XXIV OM - I - Zadanie 2

Dowieść, że spośród 25 różnych liczb dodatnich można wybrać dwie, których ani suma, ani różnica nie jest równa żadnej z pozostałych liczb.

Rozwiązanie

Oznaczmy dany zbiór liczb przez $ A = \{a_1, a_2, \ldots, a_{25}\} $, gdzie $ 0 < a_1 < a_2 < \ldots < a_{25} $. Przypuśćmy, że dla dowolnych $ r $, $ s $, gdzie $ 1 \leq r < s \leq 25 $, zachodzi: $ a_s + a_r \in A - \{a_r, a_s\} $ lub $ a_s - a_r \in A - \{a_r, a_s\} $. Oczywiście $ a_r - a_s < 0 $ i wobec tego liczba $ a_r - a_s $ nie należy do $ A $.

Ponieważ dla $ i = 1, 2, \ldots, 24 $ mamy $ a_{25} + a_i > a25 $, więc $ a_{25} + a_i \not \in A $. Zatem na mocy przypuszczenia $ 24 $ liczby $ a_{25} - a_i $ tworzą ciąg malejący o wyrazach należących do zbioru $ A - \{a_{25}\} $ o $ 24 $ elementach. Stąd

\[<br />
a_{25} - a_i = a_{25-i} \ \textrm{dla}\ i = 1, 2, \ldots, 24.<br />
\]

Ponieważ dla $ j = 2, 3, \ldots, 23 $ mamy $ a_{24} + a_j > a_{24} + a_1 = a_{25} $, więc $ a_{24} + a_i \not \in A $ i stąd na mocy przypuszczenia mamy $ a_{24} - a_j \in A $. Ponadto $ a_{24} - a_j \leq a_{24} - a_2 = (a_{25} - a_1) - (a_{25} - a_{23}) = a_{23} - a_1 < a_{23} $. Zatem $ 22 $ liczby $ a_{24} - a_j $ tworzą ciąg malejący o wyrazach należących do zbioru $ A - \{a_{23}, a_{24}, a_{25} \} $ o $ 22 $ elementach. Stąd

\[<br />
a_{24} - a_j = a_{24-j} \ \textrm{dla}\ j = 2, 3, \ldots, 23.<br />
\]

W szczególności $ a_{24} - a_{12} = a_{12} $, a więc $ a_{24} - a_{12} \not \in A - \{a_{12}, a_{24}\} $. Mamy również $ a_{24} + a_{12} > a_{24} + a_1 = a_{25} $, a więc $ a_{24} + a_{12} \not \in A $. Przeczy to początkowemu przypuszczeniu.

Komentarze

Dodaj nową odpowiedź