Tübitak Ortaokul 1. Aşama 2024 Soru 28

[matematikolimpiyati]

$9 \times 9$ bir satranç tahtasının $n$ birim karesi nasıl işaretlenirse işaretlensin, tahtanın $3$ tane işaretlenmiş birim karesinden oluşan $1 \times 3$ ya da $3 \times 1$ boyutlarında bir dikdörtgen bulunuyorsa, $n$ sayısının alabileceği en küçük değer kaçtır?

$\textbf{a)}\ 49  \qquad\textbf{b)}\ 51  \qquad\textbf{c)}\ 53  \qquad\textbf{d)}\ 55  \qquad\textbf{e)}\ 57$

[Lokman Gökçe]

Yanıt: $\boxed{D}$

İstenen özellikte bir dikdörtgen bulundurmayan bir $9 \times 9$ tahta düşünelim. Bir satırda en fazla $6$ tane işaretlenmiş kare olabilir. Çünkü, bir satırda $7$ tane işaretlenmiş kare olursa bunlardan $3$ tanesi yan yana gelmek zorundadır. Bu da $1\times 3$ türünde işaretli bir dikdörtgen oluşması demektir. Böylece tüm tahtada toplamda $9\cdot 6 = 54$ ya da daha az sayıda işaretlenmiş kare olursa, $1\times 3$ (veya $3\times 1$) türünde dikdörtgen görülmeyebilir. $54$ için bunun örneği aşağıdaki gibidir:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
& C_1 &C_ 2 & C_3 & C_4 & C_5 & C_6 & C_7 & C_8 & C_9\\
\hline
R_1 & \times & \times &  & \times & \times & & \times & \times & \\
\hline
R_2 &  & \times & \times & & \times & \times & & \times & \times \\
\hline
R_3 & \times & & \times & \times & & \times & \times & & \times\\
\hline
\end{array}$$

$R_i$'ler satırları, $C_i$'ler sütunları göstermektedir. İlk üç satırdaki düzeni üçlü blok halinde sonraki satırlarda da kullandığımızı düşünelim. $54$ işaretlenmiş kare vardır ama $1\times 3$ (veya $3\times 1$) türünde dikdörtgen görülmez. Dolayısıyla $54 + 1 = 55$ işaretlenmiş kare olduğu zaman, satırlardan birinde en az $\left\lceil \dfrac{55}{9}\right\rceil = 7$ işaretli kare bulunur. Bu satırda $1\times 3$ türünde bir işaretli dikdörtgen mutlaka vardır.