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

[Metin Can Aydemir]

$(m,n) = (32,33),\ (20,25),\ (10,40),\ (19,21),\ (77,99)$ ikililerinin kaç tanesi için $m \times n$ boyutlarındaki bir satranç tahtasının her birim karesi kırmızı ve mavi renklerinden birine, her birim karenin kendisiyle aynı renkte olan ve kendisiyle ortak kenar veya ortak köşe paylaşan birim karelerin sayısı tek sayı olacak şekilde boyanabilir?

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

[Mathtaker]

Karelerin merkezini rengine gore boyayalim. Kirmizilari $a$  ve mavileri $b$ ile gosterelim. Bir noktadan kendisiyle ayni renge giden kenar sayisini $f$ fonskiyonu ile gosterirsek $\sum{f(a_i)}$ ve $\sum{f(b_j)}$ toplamlari 2 ye bolunur, cunku her bir kenari 2 defa saydik. Her $a$ dan tek sayida kirmizi kenar cikiyor, $f(a_i)$ cift oldugundan kirmizi ve ayni mantikla mavi kareler cift sayida olmalidir. Son 2 durum elendi. Diger 3 unu 2 satir/sutun boyunca kirmizi, sonra 2 mavi vs. sekilde boyariz.

[Lokman Gökçe]

Yanıt: $\boxed{C}$

$m$ ile $n$'den en az biri çift sayı ise istenen şekilde boyamak mümkündür. $m=2\ell$ şeklinde çift sayı olduğunu varsayalım. Ardışık satırları ikişerli gruplayarak $\ell$ tane $2\times n$ türünde tahta düşünelim. Kırmızı renkli olan karelere $k$, mavi renkli olan karelere $m$ yazalım. İlk gruptaki $2\times n$ kareye $k$, ikinci gruptaki $2\times n$ tane kareye $m$, üçüncü gruptaki $2\times n$ tane kareye $k$ yazarak alterne biçimde ilerleyelim. Aşağıdaki örnek yapıyı inceleyebiliriz:

$$
\begin{array}{|c|c|c|c|}
\hline
k & k & k & \cdots & k \\\hline
k & k & k & \cdots & k \\\hline
m & m & m & \cdots & m \\\hline
m & m & m & \cdots & m \\\hline
\end{array}
$$

Bu şekilde $m \times n$ türünde tahta istenen özellikte boyanabilir.

Şimdi $m$ ve $n$ sayılarının tek sayı olduğunu düşünelim. Aynı renkli komşu kareler arasında birer çizgi çekerek bunları gösterelim. Çizge teorisi diliyle, kareleri birer köşe noktası, aynı renkteki komşulukları da birer kenar ile ile ifade edebiliriz. Her köşe noktasının derecesi $1,3,5,7$ sayılarından biri olabilir. Tüm köşe noktalarının derecelerinin toplamı, toplam kenar sayısının $2$ katına eşittir. Çünkü her kenarın iki ucu vardır. Bu uçlar komşu renkli kareleri temsil eden noktalardır. Bu temel teorem, Euler'in El Sıkışma Lemması (Handshaking lemma) ismiyle de bilinir.

Özetle, $mn$ tane (tek sayıda) köşe noktası vardır ve her köşe noktasının derecesi $1,3,5,7$ sayılarından biri olduğundan dereceler toplamı tek sayıdır. Bu sayı toplam kenar sayısının $2$ katına (çift sayıya) eşit olamaz. Böylece $m$ ve $n$ tek sayı iken bu boyamayı yapmak imkansızdır.

Münkün olan boyamalar $(m,n) = (32,33), (20,25), (10,40)$ olup $3$ tanedir.