XLIV OM - II - Zadanie 4

Niech $ (x_n) $ będzie takim ciągiem liczb naturalnych, że:

\[<br />
x_1 = 1 \quad \text{ oraz } \quad<br />
x_n < x_{n +1} \leq 2n \quad \text{ dla } n=1,2,3,\ldots .<br />
\]

Udowodnić, że dla każdej liczby naturalnej $ k $ istnieją takie liczby $ r $ i $ s $, że $ x_r - x_s = k $.

Rozwiązanie

Ustalmy liczbę naturalną $ k $. Aby znaleźć numery $ r $ i $ s $, o które chodzi w zadaniu, wystarczy rozważać początkowy odcinek ciągu $ (x_n) $, złożony z $ k +1 $ jego pierwszych wyrazów:

\[<br />
1 = x_1 < x_2 < x_3 < \ldots < x_k < x_{k + 1} \leq 2k.<br />
\]

Zbiór liczb naturalnych od $ 1 $ do $ 2k $ rozbijamy na sumę $ k $ zbiorów dwuelementowych, jak następuje:

\[<br />
\{1,2,3,\ldots,2k-1,2k\} = A_1 \cup A_2 \cup \ldots	 \cup A_{k-1} \cup A_k,<br />
\]

gdzie

\[<br />
A_1 = \{1,k+ 1\}, \quad A_2 = \{2,k + 2\}, \ldots , A_{k-1} = \{k-1,2k-1\}, A_k = \{k,2k\}.<br />
\]

Z zasady szufladkowej wynika, że spośród $ k+1 $ liczb $ x_1,x_2,\ldots,x_{k+1} $ pewne dwie (różne) trafią do jednego zbioru $ A_i = \{i,k + i\} $. Oznaczając ich numery przez $ r $ i $ s $ (gdzie $ r > s $) widzimy, że $ x_r = k + i $, $ x_s = i $. Zatem $ x_r - x_s = k $.

Komentarze

Dodaj nową odpowiedź