Tübitak Lise 1. Aşama 2018 Soru 08

[AtakanCİCEK]

$12 \times 12$ satranç tahtasının birim karelerinden $k$ tanesi kırmızı ve $k$ tanesi mavi renge, hiçbir kırmızı birim karenin hiçbir komşusu (ortak kenar veya köşeye sahip birim kareler) boyanmayacak şekilde boyanabiliyorsa, $k$ nin alabileceği en büyük değer nedir?

$\textbf{a)}\ 26 \qquad\textbf{b)}\ 27  \qquad\textbf{c)}\ 28 \qquad\textbf{d)}\ 29 \qquad\textbf{e)}\ 30$

[AtakanCİCEK]

Yanıt:$\boxed{C}$

Soruda verilen ortak kenar veya köşelere sahip birim kareler boyanmayacak şekilde $2$ sıra boyunca kırmızı ile boyayalım.
Çünkü kırmızı ortada bir yerlerde olduğunda çevresinde boyanamayacak kare sayısı artıyor. Buna göre şekli oluşturalım.
$$ \begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline   k & *  & k &  & k &  &k  &  &k  &  &k  &     \\ \hline  &  &  &  &  &  &  &  &  &  &  &      \\ \hline k &  &  & k  &  & k  &  &k  &  &  &  &  k     \\ \hline  &  &  &  &  &  &  &  &  &k  &  &     \\ \hline k &  &  &   & m &m  &m  &m  &  &  &  & k  \\ \hline  &  &k  &   & m &m  &m  & m &  &k  &  &   \\ \hline k &  &  &  &m  &m  &m  &m  &  &  &  & k   \\ \hline  &  &k  &  & m &m  & m & m &  &k  &  &    \\ \hline k &  &  &   &  &  &  &  &  &  &  & k   \\ \hline  &  & k &  & k &  & k &  & k &  &  &   \\ \hline k &  &  &  &  &  &  &  &  &  &  &k   \\ \hline  &  &k  &  &k  &  & k &  &k  &  &  &  \\  \hline   \end{array}$$
NOT: $k$ harfi kırmızı ile boyananan , $m$ harfi mavi ile boyanabilen yerleri göstermektedir.(* sembolünü birimkareleri eşitlemek için koydum önemli bir nedeni yok.)
kare boyanabilir olduğundan $30$ tane kırmızı kare ve $24$ boyanabilir dolayısıyla hala daha maksimum kırmızı kare sayısına ulaşamadık.
soldaki en üst sıradan $1$ kırmızı kare daha atalım seçtiğimiz kareye göre $25$,$26$ veya $28$ boyanabilir kare elde edilir. Fakat boyanabilir 29 kare elde edilemediğinden $1$ Kırmızı kare daha attığımızda  (Sol en üst ve $1$ altındaki kare) $16+8+4=28$ tane boyanabilir kare elde edilir. Biz kırmızı kare sayısını $32-4=28$ e indirmiştik. Dolayısıyla $k=28$ maximum alabileceği değeri olur.
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|} \hline   m &   & k &  & k &  &k  &  &k  &  &k  &     \\ \hline  m&  &  &  &  &  &  &  &  &  &  &      \\ \hline m &m  & m & m  &  & k  &  &k  &  &  &  &  k     \\ \hline  &  &m  &m  &  &  &  &  &  &k  &  &     \\ \hline k &  & m & m  & m &m  &m  &m  &  &  &  & k  \\ \hline  &  &m  & m  & m &m  &m  & m &  &k  &  &   \\ \hline k &  &  &  &m  &m  &m  &m  &  &  &  & k   \\ \hline  &  &k  &  & m &m  & m & m &  &k  &  &    \\ \hline k &  &  &   &  &  &  &  &  &  &  & k   \\ \hline  &  & k &  & k &  & k &  & k &  &  &   \\ \hline k &  &  &  &  &  &  &  &  &  &  &k   \\ \hline  &  &k  &  &k  &  & k &  &k  &  &  &  \\  \hline   \end{array}$$
NOT: $k$ harfi kırmızı ile boyanan , $m$ harfi mavi ile boyanan yerleri göstermektedir.