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

\(n > 1\) bir tam sayı olmak üzere, \(\{1, 2, \dots, n^2\}\) kümesinin \(k\) elemanlı her alt kümesinde \(x^2 \mid y\) olacak şekilde \(x\) ve \(y\) elemanları bulunuyorsa, \(k\) nin alabileceği en küçük değeri bulunuz. 


**Çözüm:**

Şıklar:

Cevap:  \(n^2 - n + 1\)

Çözüm:
**Çözüm 1:** \(\{n + 1, n + 2, \dots, n^2\}\) kümesinde \(x^2|y\) olan \(x\) ve \(y\) elemanları bulunmaz. O halde \(k \ge n^2 - n + 1\). 


Farzedelim ki \(n^2 - n + 1\) elemanlı olup \(x^2|y\) olacak şekilde \(x\) ve \(y\) içermeyen en az bir altküme bulunsun. Bunlardan elemanları toplamı en büyük olan \(A\) ve \(\min_{a \in A} a = m\) olsun. \(m = 1 \in A\) olamayacağı açık. \(|A| = n^2 - n + 1\) olduğundan \(m \le n'\)dir ve dolayısıyla \(m^2 \le n'^2\)dir. \(B = (A \setminus \{m\}) \cup \{m^2\}\) kümesini ele alalım. \(B'\)de \(x^2|y\) olan \(x\) ve \(y\) varsa, \(x = m^2\) veya \(y = m'^2\)dir. \(m^4|y\) olsaydı, \(m^2|y\) olurdu ve bu \(A'\)nın seçimi ile çelişir. \(x^2|m^2\) olsaydı, \(x|m\) ve \(x \le m\) olurdu ve bu da \(m'\)nin seçimiyle çelişir. O zaman \(B\) de aynı koşulu sağlar. Ancak, \(1 < m\) olduğundan \(B'\)nin elemanları toplamı \(A'\)nın elemanları toplamından daha büyüktür, çelişki. 


**Çözüm 2:** \(\{n + 1, n + 2, \dots, n^2\}\) kümüseinde \(x^2|y\) olan \(x\) ve \(y\) elemanları bulunmaz. O halde \(k \ge n^2 - n + 2\). 


\(n^2 - n + 1\) elemanlı bir altkümede \(x^2|y\) olan \(x\) ve \(y\) bulunduğunu ispatlayalım. Öncelikle, her \(1 \le i \le n\) için \(i^2|y_i\) olacak şekilde farklı \(n < y_1, y_2, \dots, y_n \le n^2\) tam sayılarının bulunduğunu gösterelim. Tümevarım ile göstereceğiz. \(n = 2\) için, \(y_1 = 3\) ve \(y_2 = 4\) sağlar. \(n = r \ge 2\) için koşulları sağlayan \(y_1, \dots, y_r\) bulunsun. \(y_i = r + 1\) olan \(i\) yoksa \(y_{r+1} = (r + 1)^2\) alırız ve koşullar sağlanır. \(y_i = r + 1\) olan \(i\) varsa, \(i^2|r + 1'\)dir. \(y_i = r(r + 1)\) ve \(y_{r+1} = (r + 1)^2\) alırız v e tüm şartlar sağlanır. O zaman \(n^2 - n + 1\) elemanlı herhangi bir altkümede güvercin yuvası prensibinden dolayı en az bir \(i\) için \(i\) ve \(y_i\) bulunur. 


**Çözüm 3:** \(\{n + 1, n + 2, \dots, n^2\}\)kümüseinde \(x^2|y\) olan \(x\) ve \(y \) elemanları bulunmaz. O halde \(k \ge n^2 -n + 1\). 


\(n^2 - n + 1\) elemanlı bir altkümede \(x^2|y\) olan \(x\) ve \(y\) bulunduğı unu ispatlayalım. \(S = \{1, 2, \dots, n^2\}\) olsun. \(S'\)de tam kare olmayan sayılar \(a_1, a_2, \dots, a_m\) olsun. \(m = n^2 - n\) olduğu açıktır. Her

i = 1, ..., m için \(S_i = \{a_i^{2^k} : k \in \mathbb{Z}^+ \cup \{0\}\} \cap S\) olsun. 


i ≠ j iken \(S_i \cap S_j = \emptyset\) olduğunu gösterelim. \(a_i^{2^k} = a_j^{2^l}\) olsun. Genelliği bozmadan \(k \ge l\) varsayalım. \(k = l\) olsaydı, \(a_i = a_j\) yani \(i = j\) olurdu. O halde \(k > l\). O zaman \(a_i^{2^{k-l}} = a_j\) olur ve bu da \(a_j\)'nin tam kare olması demektir, çelişki. 


\(S'\)de 1'den farklı her elemanın bir \(S_i\)'ye ait olduğunu gösterelim. \(x \in S\) ve \(x > 1\) olsun. \(x^{\frac{1}{2^k}}\)'nın tam sayı olduğu en büyük negatif olmayan \(k\) tam sayısı \(r\) olsun. O zaman \(x^{\frac{1}{2^r}}\) bir tam sayıdır ve tam kare değildir. Dolayısıyla \(S'\)de yer alır ve \(a_i = x^{\frac{1}{2^r}}\) olan \(i\) vardır. O halde \(x \in S_i\) olur. 


\(n^2 - n + 1\) elemanlı bir altkümede 1 yer alıyorsa koşul açıkça sağlanır. 1 yer almıyorsa, güversin yuvası prensibinden dolayı en az bir \(S_i\) için bu kümede \(S_i'\)den iki eleman vardır ve bu iki sayı koşulu sağlar.