Tübitak Lise 1. Aşama 2016 Soru 04

[mehmetutku]

$24 \times 24$ satranç tahtasının bazı birim karelerine birer taş nasıl yerleştirilirse yerleştirilsin, her taşı $k$ renkten birine, aynı satır veya aynı sütun üzerinde olup aralarında başka taş bulunmayan herhangi iki taşın rengi farklı olacak şekilde boyayabiliyorsak, $k$ nın alabileceği en küçük değer nedir?

$\textbf{a)}\ 2 \qquad\textbf{b)}\ 3  \qquad\textbf{c)}\ 4 \qquad\textbf{d)}\ 5 \qquad\textbf{e)}\ 6$

[Lokman Gökçe]

Yanıt $\boxed{B}$

Eğer tüm karelere taş koyulmuşsa, ortak kenara sahip karelerde farklı renklerde taş olacağından $A$ ve $B$ ile göstereceğimiz iki farklı renkle boyama yapılabilir. Ancak bazı karelere taş konulmamışsa iki rengin yetmeyeceğini gösterelim. Şekildeki gibi $21$ kareye taş koyulmuş olsun. İki renk ile boyamaya başlarsak aşağıdaki desen oluşur. $?$ ile gösterdiğimiz karedeki taşın dört kare solunda $A$ rengi olduğu için $?$ karesini $A$ ile boyayamayız. Ayrıca $?$ karesinin üstündeki karede de $B$ rengi olduğundan $?$ karesindeki taşı $B$ ile de boyayamayız. Böylece $?$ karesi için üçüncü bir $C$ rengi kullanmamız gerektiğini anlarız. $k \geq 3$ tür.

Genel olarak bir karedeki taşın rengini kısıtlayan iki unsur vardır. Bunlar, o taşın üstündeki ilk taş ile o taşın solundaki ilk taştır. Üstünde ve solunda $A$, $B$ renkli taş bulunan taşı $C$ rengiyle boyarız. Üstünde ve solunda $A$, $C$ renkli taş bulunan taşı $B$ rengiyle boyarız. Üstünde ve solunda $B$, $C$ renkli taş bulunan taşı da $A$ rengiyle boyarız. Elbette üstünde ve solunda aynı renkli, örneğin $A$, $A$ taşları bulunan taşı $B$ ya da $C$  renginden istediğimiz herhangi biriyle boyayabiliriz. $k=3$ tür.