Matematik Olimpiyatı 2024, 2. Aşama, Soru 6

\(m, n \ge 2\) tam sayılar olmak üzere, \(m \times n\) satranç tahtasının bazı birim karelerine birer kale, her kale tek sayıda kale tarafından tehdit edilecek şekilde yerleştirilmiştir. Buna göre, satranç tahtasının üzerindeki kale sayısının alabileceği en büyük değeri bulunuz.

Şıklar:

Cevap:  \(N(m, n)\), \(m\) satır ve \(n\) sütundan oluşan tahtaya yerleştirebilecek en büyük kale sayısı olmak üzere, \(N(2, 2) = 2\), \(N(2, 3) = 4\) ve tüm diğer durumlarda \(N(m, n) = 2m + 2n - 8\)

Çözüm:
Cevap: \(N(m, n)\), \(m\) satır ve \(n\) sütundan oluşan tahtaya yerleştirebilecek en büyük kale sayısı olmak üzere, \(N(2, 2) = 2\), \(N(2, 3) = 4\) ve tüm diğer durumlarda \(N(m, n) = 2m + 2n - 8\). 


Örnekler: 


\(m = 2\) için 

  


  


  


veya 

  

\(m = 3\) için 

  


\(m, n \ge 4\) için 

  


Şimdi ise satranç tahtası üzerindeki kale sayısının daha fazla olamayacağını gösterelim. 


Yukarı, aşağı, sağ ve sol olmak üzere, 4 yön tanımlayalım. Her keleden onu tehdit etmeyen yönlere doğru ışınlar çizelim. Bu ışınlardan her biri satranç tahtasının 1 uzunlukta bir birim sınır kenarını kesiyor. İki farklı ışın 1 uzunluktaki aynı birim kenarı kesemez. Bir kale tarafından tehdit edilen kalelere tek kale, üç kale tarafından tehdit edilen kalelere üçlü kalesi diyelim. Her tek kaleyle onun ışınlarının kestiği üç birim kenarı eşleyelim. Her üçlü kaleyle onun ışınlarının kestiği bir birim kenarı eşleyelim.

**Lemma 1:** Tek kale sayısı en az 4 ise toplam kale sayısı en fazla \(2m + 2n - 8\) dir.


İspat: Tek kale sayısı \(a\), üçlü kale sayısı \(b\) olsun. Dört tek kalenin her biriyle üçer birim kenar, her üçlü kaleyle bir birim kenar eşleşmek zorundadır. Satranç tahatsının kenar uzunluğu \(2m + 2n\) olduğundan \(3a + b \le 2m + 2n\) olur. Demek ki \(a \ge 4\) ise, \(a + b \le 2m + 2n - 2a \le 2m + 2n - 8\). İspat tamamlanmıştır.


**Lemma 2:** \(m, n \ge 3, m + n \ge 7\) ve \(N(m, n) \ge 2m + 2n - 8\) olsun. O zaman tek kale sayısı en az \(4^2\) tür.


İspat: Satranç tahtasının en az bir kale içeren en yukarıdaki satırı \(S_1\) en aşağıdaki satırları \(S_2\), en en soldaki sütunu \(T_1\) ve en sağdaki sütu \(T_2\) olsun. \(S_1, S_2, T_1\) ve \(T_2\) birer kale bulunduruyorsa bu kaleler birbirinden farklıdır ve bu dört kalenin her biri tek kaledir. \(S_1, S_2, T_1\) ve \(T_2\), den en az ikisi en az iki kale bulunduruyorsa bu yine bu kalelerden uç kale olan 4 kale tek kaledir. Son olarak genelliği bozmadan \(S_1\) üzerinde en az iki ve \(S_2\) üzerinde bir kale olsun. O zaman \(S_1\) üzerindeki 2 uç kale ve \(S_2\) üzerindeki kale tek kaledir. \(2m + 2n - 8 \ge \max(m, n) + 2\) olduğuna göre, \(S_1\) dışında en az 2 kale vardır. \(S_2\) üzerindeki tek kale \(A\) olsun. En az bir kale bulunduran ve \(S_2\)'e en yakın olan satır \(S'\) olsun. \(S'\) in üzerinde bir kale varsa bu kale tek kaledir. \(S'\) in üzerinde birden fazla kale varsa \(S'\) in üzerindeki \(A\) ile aynı sütunda olmayan uç kaleler tek kaledir. İspat tamamlanmıştır.


**Lemma 2** ve **Lemma 1**'e göre, \(m, n \ge 3\), \(m + n \ge 7\) ise \(N(m, n) \le 2m + 2n - 8\). Şimdi de kalan durumları inceleyelim.


\(m = 2\). Her satırdaki en sol ve en sağ kaleler tek kale olmak zorundadır. \(N(2,2) \ge 3\) olursa, en az bir satırda 2 kale bulunuyor. O zaman bu iki kale tek kaledir ve sonuç olarak ikinci satırda kale bulunmuyor, çelişki. \(N(2,3) \ge 5\) olursa, her satırda en az 2 kale bulunuyor. Demek ki her satırda en az iki tek kale bulunuyor. Bu 4 tek kaleyle toplam 12 birim kenar eşleşmek zorunda, fakat birim kenar satısı 10, çelişki. \(N(2,4) \ge 5\) olsun. Her satırda en az iki kale varsa, toplamda en az 4 tek kale vardır ve Lemma'ya göre, \(N(2,4) \le 2 \cdot 2 + 2 \cdot 4 - 8 = 4\), çelişki. Bir satırda 4, diğer satırda 1 kale varsa, 4 kale bulunduran satırda 2 kale tarafından tehdit edilen kale vardır, çelişki. \(k \ge 5\) durumunda \(N(2,k) > 2k - 4\) olursa, \(2k - 4 \ge k + 1\) olduğundan \(N(2,k) \ge k + 1\). Demek ki her satırda en az 2 kale bulunuyor, ve dolayısıyla en az 4 tane tek kale vardır. Lemma'ya göre, toplam kale sayısı en fazla \(2n - 4\), çelişki.


\(m = 3\). \(N(3,3) \le 4\) olduğunu gösterelim. 4 tane tek kale varsa, Lemma'ya göre, en fazla 4 kale vardır. Demek ki \(N(3,3) \ge 5\) olması için en az 2 tane üçlü kale olmak zorundadır. Fakat bu durumda her biri 3 kale bulunduran ya iki satır, ya iki sütun ya da bir satır ve bir sütun vardır. O zaman tahtanın 4 köşe birim karesinden en az üçünde kale vardır, çelişki.


Çözüm tamamlanmıştır.