Dikdörtgen Oluşturmadan Maksimum Sayıda Kutu Karalama Sorusu ve Çözüm için Bir Alt Sınır

Authors : Ceren Sahin

Pages : 48-53

Doi:10.37215/bilar.1037944

View : 17 | Download : 11

Publication Date : 2022-09-07

Article Type : Research

Abstract :Bu çalışmanın amacı henüz çözülemediği iddia edilen Dikdörtgen Oluşturmadan Maksimum Sayıda Kutu Karalama Sorusu’nun çözümü için bir alt sınır sunmaktır. Makale boyunca Dikdörtgen Oluşturmadan Maksimum Sayıda Kutu Karalama Sorusu adıyla anılan soru şu şekildedir: n × m lik bir çizelgede dikdörtgen oluşturulmadan en fazla kaç kutu karalanabilir? Öncelikle sorunun Sonlu Matematikte çokça kullanılan güvercin yuvası ilkesiyle ilgili olduğu fark edilmiştir. Daha sonra sorunun bir alt versiyonları incelenmiştir. Sorunun bir alt versiyonu her satırda en fazla y sayıda kutu karalanırsa ne olur, z tane renk kullanılırsa ne olur tarzında çözülebilir sorulardır. Bu soruyla bir alt versiyonu arasındaki ilişki gözetilerek problemin çözümü için bir alt sınır oluşturulmuştur. Soru iki farklı durumda incelenmiştir. Birinci duruma doğrudan ispat tekniğiyle çözüm bulunmuştur. İkinci duruma doğrudan ispat tekniği ve kodlamadan yararlanılarak bir alt sınır bulunmuştur. Bulunan sonucun doğruluğu bolca örnekle test edilmiştir. Sonuç olarak, genelliği bozmadan n ≤ m alındığında, n satır ve m sütunluk bir çizelgede C(n, 2) ≤ m ise dikdörtgen oluşturmadan karalanabilecek maksimum kare sayısı C(n, 2) + m olarak bulunmuştur. C(n, 2) > m ise dikdörtgen oluşturmadan karalanabilecek maksimum kare sayısı için bir alt sınır bulunmuştur. Bu alt sınır 2m + x ‘tir. Bahsedilen x değişkeni bir kod yazarak bulunmuştur ve m, n sayılarının değerine göre değişir.
Keywords : Sonlu Matematik, Boyama İlkesi, Güvercin Yuvası İlkesi