Tübitak Lise Takım Seçme 2015 Soru 5

[mehmetutku]

$2015\times2015$ satranç tahtasının birim kareleri; ikisi aynı sütunda ve üçüncüsü bu iki kareden daha yukarıdakiyle aynı satırda ve ondan sağda veya bu iki kareden daha aşağıdakiyle aynı satırda ve ondan solda olan herhangi üçü aynı renge boyanmayacak koşuluyla $k$ renge boyanabiliyorsa, $k$ nın alabileceği en küçük değer nedir?

(Azer Kerimov)

[MATSEVER 27]

Yanıt $k=1008$.

$2015 \times 2015$ satranç tahtasının birim karelerinden oluşan $(u_1, u_2, u_3)$ üçlüsüne; $u_1$ ve $u_2$ aynı sütunda, $u_1$ karesi $u_2$ den daha yukarıda, $u_3$ karesi $u_2$ ile aynı satırda ve $u_2$ den sağda ise L-üçlüsü diyelim.

Renklerden biri kırmızı olsun. Kırmızı renge boyalı birim karelerin sayısının en fazla $4029$ olduğunu gösterelim. Her satırın kırmızı birim karelerinin en sağdakini işaretleyelim. O zaman L-üçlüsünün oluşmaması için her sütunda en fazla bir işaretlenmemiş kırmızı birim kare olabilir (sonuncu sütunda işaretlenmemiş kare zaten olamaz). Demek ki en fazla $2015$ işaretlenmiş ve $2014$ işaretlenmemiş kırmızı birim kare olabilir. Buradan $k \geq \frac{2015 \cdot 2015}{ 4029} > 1007$. $ k = 1008$ için örnek: satırları yukarıdan aşağıya, sütunları soldan sağa $1, 2, \dots , 2015$ sayılarıyla numaralandıralım ve $i.$ satırla $j.$ sütunun kesişiminde bulunan $(i, j)$ karesini $\lfloor{\frac{(i+j) \pmod{2016}}{2}}\rfloor$ ile boyarsak sağlar.