Scratching Maximum Number of Boxes Without Forming a Rectangle and A Lower Bound for the Solution

Year 2022, , 48 - 53, 07.09.2022

Ceren Sahin

https://doi.org/10.37215/bilar.1037944

Abstract

The aim of this study is to present a lower bound for the solution to the unsolved question
“Scratching Maximum Number of Boxes Without Forming a Rectangle’’. The question that will
be referred to as the “Scratching Maximum Number of Boxes Without Forming a Rectangle’’
throughout the article is: How many boxes can be scratched in a m × n table without forming a
rectangle? Firstly, it has been noticed that the problem is related to the pigeonhole principle,
which is widely used in Finite Mathematics. Later, subversions of the question were examined.
Subversions of the problem are solvable questions such as what happens if at most y boxes are
scribbled on each line, and what happens if z colours are used. Considering the relationship
between this question and the subversions, a lower bound was created to solve the problem. The
problem was considered in 2 cases. The direct proof technique was used to solve the first case
of the problem. A lower bound was found for the second case of the problem with the help of the
direct proof technique and coding. The accuracy of the result found has been tested with lots of
samples. As a result of the study, if n ≤ m is taken without breaking the generality, if C(n, 2) ≤ m
in a table with n rows and m columns, the maximum number of squares that can be drawn without
forming a rectangle is C(n, 2) + m. If C(n, 2) > m, a lower bound has been found for the maximum
number of squares that can be drawn without forming a rectangle. This lower bound is 2m + x.
The mentioned variable x was found by writing a code that changes according to the values of m,
n numbers.

Keywords

Finite Mathematics, Painting Principle, Dirichlet Principle

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

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

References

• Alizade, R. (2015). Sonlu Matematik: Altın Nokta Yayınları. İzmir – Türkiye.
• Anonim 1 (2003). “Karenin Dikdörtgensiz Altkümeleri”. Matematik Dünyası Dergisi. 4 (1):62