Matematik Olimpiyatı 2020, 2. Aşama, Soru 6

Bir çember üzerindeki 2021 noktadan her biri \(1, 2, \dots, k\) renklerinden birine boyanmıştır. Her nokta ve her \(1 \le r \le k\) rengi için bu noktayı içeren ve üzerindeki noktaların en az yarısının \(r\) renginde olduğu bir yay bulunuyor. Buna göre, \(k\) nin alabileceği en büyük değeri bulunuz.

Şıklar:

Cevap:  2

Çözüm:
Çember üzerindeki 2021 noktayı her noktanın en az bir komşusu kendisiyle aynı renkte olmayacak şekilde 2 renge boyarsak koşullar sağlanır. 


Şimdi \(k < 3\) olduğunu göstereceğiz. Her yayı, bu yayın içindeki uç noktalarla temsil edeceğiz: üzerindeki noktalar saat yönünde sırasıyla \(A, B, \dots, Z\) olan yay \((A, Z)\) olarak işaretlenecektir. Bir \(r\) rengi ve \(r\) rengine boyalı olmayan herhangi bir \(A\) noktası için koşulları sağlayan yaylardan en az sayıda nokta içeren yay \(l_A(r) = (B, C)\) olsun.

Gözlem 1. \(l_A(r) = (B, C)\) ise ya \((B, C) = (B, A)\) ya da \((B, C) = (A, C)\) olacaktır. 


Aksini varsayalım. \((B, A)\) yayındaki nokta sayısı \(m\), \(r\) rengine boyalı nokta sayısı ise \(b\), \((A, C)\) yayındaki nokta sayısı \(n\), \(r\) rengine boyalı nokta sayısı ise \(c\) olsun. O zaman \(\frac{b}{m} < \frac{1}{2}\) ve \(\frac{c}{n} < \frac{1}{2}\) olur. Buradan \(2b \le m - 1\) ve \(2c \le n - 1\) gelir. Buna göre, 


\[2b + 2c \le m + n - 2 < m + n - 1 \text{ ve sonuç olarak } \frac{b+c}{m+n-1} < \frac{1}{2}\]


elde edilir. Bu da \(l_A(r) = (B, C)\) yayının koşulları sağladığı ile çelişiyor. 


Şimdi genelliği bozmadan \(r\) rengi ve \(r\) rengine boyalı olmayan herhangi bir \(A\) noktası için \(l_A(r) = (A, C)\) olsun. Tanımlara göre, \(C\) noktası \(r\) rengindedir. 


Gözlem 2. \((A, C)\) yayındaki nokta sayısı \(n\), r rengine boyalı nokta sayısı ise \(c\) olsu. O zaman \(\frac{c}{n} = \frac{1}{2}\). 


Aksini varsayalım: \(\frac{c}{n} > \frac{1}{2}\) olsun. O zaman \(2c > n\) ve \(2c \ge n + 1\) olur. Buna göre, 


\[2c - 2 \ge n - 1 \text{ ve } \frac{c-1}{n-1} \ge \frac{1}{2}\]


elde edilir. Bu da \((A, C)\) yayının en az sayıda nokta içeren yay olması ile çelişiyor. 


Gözlem 3. \(r\) rengi ve \(r\) rengine boyalı olmayan \(A\) ve \(B\) (\(A \neq B\)) noktaları için \(l_A(r) = (A, C)\) ve \(l_B(r) = (B, D)\) olsun. O zaman \(C \neq D\). 


Aksini varsayalım: \(C = D\) olsun. Genelliği bozmadan Genelliği bozmadan \(B \in (A, C)\) olduğunu varsayalım. \(A\) noktasından saat yönünde ilerlerken \(B\) den önceki nokta \(T\) olsun. Gözlem 2 ye göre, \(AC\) yayında \(r\) renkli noktaların oranı ile \(BC\) yayında \(r\) renkli noktaların oranı \(\frac{1}{2}\) dir. Buna göre \((A, T)\) yayında da \(r\) renkli noktaların oranı \(\frac{1}{3}\) olacaktır. Bu ise, \((A, C)\) yayının \(A\) noktası ve \(r\) rengi için koşulları sağlayan ve en sayıda nokta içeren yay olması ile çelişiyor.

\(k \ge 3\) olsun. O zaman en fazla 673 noktanın boyalı olduğu bir renk vardır, bu renk 1 olsun. 1 rengine boyalı olmayan her \(A\) noktası için Gözlem 1 e göre, \(l_A(r)\) yayı ya \((A, E)\) ya da \((F, A)\) şeklindedir (\(E\) ve \(F\) noktaları 1 rengindedir). Gözlem 3 e göre, 1 rengine boyalı her nokta bu tür yaylardan en fazla ikisinin uç noktası alabilir. 1 rengine boyalı olmayan nokta sayısı en az 1348 ve 1348 > 2·673 olduğuna göre, çelişki elde edilir. İspat tamamlanmıştır.