Dama Tahtası Problemi 1999 - USAMO (ABD Mat. Olimpiyatı)

Question

$ \color{red}{\textbf{Problem (1999-USAMO)}}$ $n \times n$ dama tahtasına bazı dama taşları aşağıdaki kurallara göre yerleştirilecektir:

$(a)$ Dama taşı içermeyen her kare, dama taşı olan bir kareyle ortak bir kenara sahiptir.

$(b)$ Dama taşları içeren herhangi iki kare çifti verildiğinde; verilen karelerle başlayan ve biten, dama taşları içeren bir kareler dizisi vardır ve bu dizinin her iki ardışık karesi bir ortak kenara sahiptir.

Tahtada en az $\dfrac{n^{2}-2}{3}$ dama taşı olduğunu kanıtlayınız.

 

 

$ \color{blue}{\textbf{Bazı Anekdotlar ve Bilgiler:}}$

$\color{blue}\bullet $ Problem ABD'de lise öğrencilerine sorulmuş olsa da, çözüm yöntemi olarak çizge teorisi içerdiği için lisans düzeyi olarak etiketlemeyi daha uygun gördüm.

$\color{blue}\bullet $ İlk önce klasik kombinatorik yöntemlerle problemi çözmeyi denedim ama genel bir çözüm bulmayı başaramadım. "Çözüm Öncesi Motivasyonu" başlığı altında ilk çözüm girişimlerimi paylaşacağım.

$\color{blue}\bullet $ Matematikte bilmediğim bazı özel konulara uğraşmama sebep olan bazı problemler olmuştur. Temel bir bilgi  sahibi olduğum çizge teorisine daha fazla yüklenmem için beni motive şey de bu problem oldu. Benim için zihinsel açıdan köşe taşı olan sorulardan biridir. Şimdi düşündüm de, benim için köşe taşı olmuş olan bu tür özel problemler için bir liste oluşturmak iyi olabilir. Üzerinde çok düşündüğümüz bir konuyu daha derinlemesine öğrenebiliyoruz. Bunları sunarken de dinleyicilere güzel biçimde anlatabilme fırsatı oluyor. Daha önce yapılmış çözümlerden faydalanarak, problemin titiz bir çözümünü hazırlamaya çalıştım. Biraz daha düşünmek için kendime de süre tanıyacağım ve çözümü bir süre sonra paylaşacağım.

 

$ \color{blue}{\textbf{Çözüm Öncesi Motivasyonu:}}$

$n \in \{2, 3 , 4, 5, 6 \}$ durumlarını inceleyelim.
$
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \circ   \\ \hline
\text{ } & \circ  \\ \hline
\end{array}
\quad
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ & \text{ } \\ \hline
\textbf{} & \circ & \text{ } \\ \hline
\end{array}
\quad
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \circ & \circ & \text{ }  \\ \hline
\text{ } & \circ & \circ & \text{ }  \\ \hline
\text{ } & \circ & \circ & \text{ }  \\ \hline
\text{ } & \circ & \circ & \text{ }  \\ \hline
\end{array}
\quad
\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \circ & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ & \circ    & \circ & \text{ } \\ \hline
\end{array}
\quad
\begin{array}{|c|c|c|c|c|c|}
\hline
\text{ } & \circ & \text{ } & \circ & \circ    & \circ \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } & \circ \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } & \circ \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } & \circ \\ \hline
\text{ } & \circ & \text{ } & \circ & \text{ } & \circ \\ \hline
\text{ } & \circ & \circ    & \circ & \text{ } & \circ \\ \hline
\end{array}
$

Şimdi de $n$ yi çift/tek sayı yönünden inceleyelim.

$\bullet $ $n=5$ için olan tablodaki durumu genelleştirelim. $n\geq 5$ ve $n$ bir tek sayı ise, en az $ n\cdot \dfrac{n-1}{2} + \left(  \dfrac{n-1}{2} - 1\right) = \dfrac{n^2 - 3}{2}$ tane dama taşı kullanılır.
$\bullet $ $n=6$ için olan tablodaki durumu genelleştirelim. $n\geq 6$ ve $n$ bir çift sayı ise, en az $ n\cdot \dfrac{n}{2} + \left(  \dfrac{n}{2} - 1\right) = \dfrac{n^2 + n - 2}{2}$ dama taşı kullanılır. Bu durumda, $\dfrac{n^2 + n - 2}{2} \geq \dfrac{n^2 - 3}{2} $ olur.

Bunlar sezgisel çizimlerdir. Bağlantılı bir grafik oluşturmamız gerektiğine dikkat edilmelidir. Çizge teorisinin fikirleri kullanılarak kesin bir kanıt yapılabilir. Örneğin, yukarıdaki analizimiz aşağıdaki şekli kapsamamaktadır.

$$
\begin{array}{|c|c|c|c|c|c|}
\hline
\circ    & \circ    & \circ    & \circ    & \circ & \text{ } \\ \hline
\circ    & \text{ } & \circ    & \text{ } & \circ & \text{ } \\ \hline
\color{red}\bullet    & \text{?} & \text{ } & \text{ } & \circ & \text{ } \\ \hline
\text{?} & \color{red}\bullet    & \text{ } & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ    & \text{ } & \text{ } & \circ & \text{ } \\ \hline
\text{ } & \circ    & \circ    & \circ    & \circ & \text{ } \\ \hline
\end{array}
$$

Öte yandan, çözümümüzü geliştirebiliriz. Kırmızı ile gösterdiğimiz çapraz konumlu damalara dikkat edelim. Yanında soru işareti olan hücreler boştur. Damalarımızın birbiriyle bağlantılı olması gerektiğinden; çapraz konumlu kırmızı dama taşları, düzenlememizde sadece bir kez görünebilir. Yani, minimum sayıda dama taşı kullanarak oluşturduğumuz bir konfigürasyonun farklı kısımlarında çapraz konumlu kırmızı damalar oluşursa, bağlantılılık özelliği kaybedilecektir. Kırmızı damalar, bağlantılı damaların başlangıç ve bitiş noktaları olarak düşünülebilir. Yukarıdaki çizdiğimiz $6\times 6$ türündeki tahtada ekstra damalara ihtiyacımız yok. Minimum sayıda dama taşı kullanıldığında döngü oluşmadığını gözlemliyoruz. Ayrıca, şekilde ağaç çizgesinin oluşutuğunu da gözlemliyoruz.

Bu gözlemler çizge teorisine geçiş yapmamız için yeterince motivasyon sağlıyor.

Answer 1

Açıklamada $4\times 4$ tahta için $8$ dama taşının yeterli olduğu bir örnek vermiştim. Biraz daha düşününce $7$ dama taşı ile de bu mümkün olmaktadır. Örnek durum şöyledir: 

\begin{array}{|c|c|c|c|c|}
\hline
\text{ } & \circ & \text{ } & \text{ }  \\ \hline
\text{ } & \circ & \circ & \circ  \\ \hline
\text{ } & \circ & \text{ } & \circ  \\ \hline
\text{ } & \circ & \text{ } \text{ }  \\ \hline
\end{array}

Her $n$ pozitif tam sayısı için, gerekli olan minimum dama taşı sayısını hesaplamaya çalışmanın zorluğunu gmrmüş oluyoruz. Bulduğumuz bir değerin, minimum dama taşı sayısı olduğundan emin olmamız gerekir. Şimdi çizge teorisi ile çözümüne başlayalım.

 

İçine dama taşı koyduğumuz karelerin merkezlerini işaretleyelim ve bu noktaları bir çizgenin köşeleri olarak düşünelim. Ayrıca, içinde dama taşı bulunan ve ortak kenara sahip iki karenin merkezlerini birleştirelim. Bu şekilde bir çizge elde ederiz. Bu çizgenin kapsayıcı ağacı (spanning tree) $T$ olsun. $T$ nin köşe sayısına $m$ diyelim. Amacımız, $ m \geq \dfrac{n^2-3}{2}$ olduğunu göstermektir.

Tahtada, içinde dama taşı olmayan (boş) karelerin sayısı $b$ ile gösterelim.

$$ b + m = n^2 \tag{1}$$

dir. $T$ çizgesinde her noktanın derecesi en fazla $4$ olabilir. Çünkü o noktanın sağında, solunda, üstünde veya altında bir başka dama taşı olan komşu kareler bulunabilir. Böylece boş karelerin sayısını, dama taşı olan kareler yardımıyla sayabiliriz. Bir $v\in T$ köşesi için, $v$ ye komşu olan dolu karelerin sayısı $\deg(v)$ olduğundan, komşu boş karelerin sayısı en fazla $4 - \deg(v)$ olabilir. Böylece

$$ \sum_{v\in T} (4 - \deg(v)) \geq b \tag{2}$$ olur. Ağaç çizgenin kenar sayısı özelliğini kullanırsak, $$ \sum_{v\in T} \deg(v) = 2|E| = 2(m-1) \tag{3}$$

elde ederiz. $(2), (3)$ bağıntılarını $(1)$ de yazarsak $4m - 2(m-1) + m \geq n^2 \implies 3m + 2 \geq n^2 $ olup

$$ m\geq \dfrac{n^2 - 2}{3} $$

sonucuna ulaşılır $\blacksquare$