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

[Metin Can Aydemir]

$45 \times 45$ satranç tahtasının her birim kenarı kırmızı ve mavi renklerinden birine, her birim karenin kırmızı kenarlarının sayısı tek sayı olmak koşuluyla kaç farklı şekilde boyanabilir?

$\textbf{a)}\ 2^{2025} \qquad\textbf{b)}\ 2^{2115}\qquad\textbf{c)}\ 3^{2070}-2^{2070}\qquad\textbf{d)}\ 3^{990}-2^{990}\qquad\textbf{e)}\ 4^{2025}$

[geo]

Yanıt: $\boxed B$

$a_n$ ile $n\times n$ satranç tahtasının istenen koşulda kaç farklı şekilde boyanabileceğini ifade edelim.

Bir karenin $3$ kenarını boyadıktan sonra son kenar tek bir şekilde boyanır. Örneğin, $3$ kenarın sonunda çift sayıda kenar kırmızı ise son kenar kırmızı; aksi halde maviye boyanır.
O halde, $n=1$ için $a_1 = 2^3$ tür.

$n\times n$ bir satranç tahtasının istenen şekilde boyandığını varsayalım. Şimdi de aşağıdaki şekildeki gibi $(n+1) \times (n+1)$ tahta oluşturmaya çalışalım.

Örnek: $n=3$
$\begin{array}{|c|c|c}
\hline
& & & \\ \hline
& & & \\ \hline
& & & \\ \hline
& & &
\end{array}$

Yeni çizilen her bir kenar için (toplam $2(n+1) = 2n+2$), $2$ renk seçeneğinden istediğimizi kullanabiliriz.
Tahtanın sağ alt köşesi hariç, diğer karelerin eksik kenarları tek bir şekilde seçilmek zorunda.
Tahtanın sağ alt köşesi ise eksik kenarlardan birini istediğimiz şekilde boyadığımız takdirde diğeri tek bir şekilde seçilmek zorunda.
O halde, $a_{n+1} = a_n \cdot 2^{2n+3}$ tür.

$\begin{array}{rcl}
a_1 &=& 2^3 = 2^{2\cdot 0 + 3} \\
a_2 &=& a_1 \cdot 2^{2\cdot 1 + 3} \\
a_3 &=& a_2 \cdot 2^{2\cdot 2 + 3} \\
\vdots \\
a_{n} &=& a_{n-1} \cdot 2^{2\cdot (n-1) + 3}
\end{array}$
Taraf tarafa çarparak $a_n = 2^{\displaystyle \sum_{i=0}^{n-1} 2i + 3} = 2^{3n + (n-1)n} = 2^{n^2 + 2n} = 2^{(n+1)^2 - 1}$ elde ederiz.

Soru özelinde; $a_{45} = 2^{46^2 - 1} = 2^{2115}$ olur.

[geo]

Aşağıdaki şekildeki $(n+2)n$ kenarı (tahtanın bütün sütunlarını ve ilk satırını) istediğimiz şekilde boyayabiliriz. Geriye kalan kenarlar, sırasıyla yukarıdan aşağıya, diğerlerinin durumuna göre tek seçeneğe indirgenir.

$\begin{array}{|c|c|c|c|c|c|}
\hline\\
& & & & & \\
& & & & & \\
& & & & & \\
& & & & & \\
\end{array}$

Dolayısıyla aradığımız yanıt, $2^{n^2+2n}=2^{45^2+90}=2^{2115}$ tir.

[Lokman Gökçe]

Yanıt: $\boxed{B}$

Genel olarak $m \times n$ türünde bir tahta için çözüm verelim. Her bir karenin kenarlarını $e_1, e_2, e_3, e_4$ gibi değişkenlerle ifade edelim. Eğer bir kenar kırmızı ise $e_i = 1$, mavi ise $e_i = 0$ olsun. Kırmızı renkli kenar sayısı tek sayı olması için $$e_1 + e_2 + e_3 + e_4 \equiv 1 \pmod{2}$$ olmalıdır. Her bir kareden elde edilen bu tür denklemler (denklikler) sağlanmalıdır. $mn$ tane kare olduğu için $mn$ tane denklem elde ederiz.

Öte yandan, karelerden gelen toplam kenar sayısı $m(n+1) + n(m+1) = 2mn + m + n$ olur. Dolayısıyla $2mn + m + n$ tane $e_i$ değişkenimiz vardır.

$mn$ tane denklemin her birinin birbirinden bağımsız olduğunu gözlemleyelim. En üstteki karelerden başlayarak, her bir birim kareyi incelediğimizde, birim karelerin alt kenarlarında bulunan değişken, daha önceki karelerde bulunmayan bir değişkendir. Yani $mn$ tane denklemin her biri, geri kalan diğer denklemlerden bağımsızdır. Bağımsız denklem sayısı $mn$'dir. Buna lineer cebir diliyle denklem sisteminin rank'ı diyebiliriz.

O halde sistemdeki bağımsız bilinmeyenlerin sayısı
$$\text{bilinmeyen sayısı} - \text{rank} = 2mn + m + n - mn = mn + m + n$$
olarak bulunur.

Bağımsız bilinmeyenlerin her biri $0$ veya $1$ değerini alabilir. Dolayısıyla farklı boyamaların sayısı $2^{mn + m + n}$ olur.

Problem özelinde $m=n=45$ alınırsa $45^2 + 2\cdot 45 = 2115$ olduğundan $2^{2115}$ farklı boyama elde edilir.