XLIV OM - II - Zadanie 4

Zawody matematyczne:

XLIV OM, 1992-1993

Etap:

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

$ x_1 = 1 \quad \text{ oraz } \quad x_n < x_{n +1} \leq 2n \quad \text{ dla } n=1,2,3,\ldots . $

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:

$ 1 = x_1 < x_2 < x_3 < \ldots < x_k < x_{k + 1} \leq 2k. $

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

$ \{1,2,3,\ldots,2k-1,2k\} = A_1 \cup A_2 \cup \ldots \cup A_{k-1} \cup A_k, $

gdzie

$ A_1 = \{1,k+ 1\}, \quad A_2 = \{2,k + 2\}, \ldots , A_{k-1} = \{k-1,2k-1\}, A_k = \{k,2k\}. $

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$ .