XLIII OM - I - Zadanie 9

Dowieść, że wśród dowolnych $ n+2 $ liczb całkowitych istnieją takie dwie, których suma lub różnica dzieli się przez $ 2n $.

Rozwiązanie

Oznaczmy rozważane liczby przez $ k_1,\ldots,k_{n+2} $ i niech $ r_i $ będzie resztą z dzielenia $ k_i $ przez $ 2n $.

Przypuśćmy, że wśród tych reszt są dwie równe:

\[<br />
r_i = r_j \quad \textrm{dla pewnych} \quad i,j,\ i \ne j.<br />
\]

Wówczas różnica $ k_i - k_j $ dzieli się przez $ 2n $; teza zachodzi.

Przypuśćmy z kolei, że wśród reszt $ r_1, \ldots, r_{n+2} $ nie ma dwóch równych. Reszty te są więc różnymi elementami zbioru $ \{0,1,\ldots,2n- 1\} $. Co najmniej $ n $ spośród nich nie równa się ani $ 0 $ ani $ n $; zmieniając w razie potrzeby numerację możemy przyjąć, że to reszty $ r_1,\ldots ,r_n $ są różne od $ 0 $ i $ n $, czyli należą do zbioru

\[<br />
\{1,\ldots,n-1\} \cup \{n+1,\ldots,2n-1\}.<br />
\]

Zbiór ten jest sumą następujących zbiorów dwuelementowych:

\[<br />
\begin{split}<br />
A_1    = & \{1, 2n - 1\}, \\<br />
A_2    = & \{2,2n-2\}, \\<br />
\vdots \\<br />
A_{n-1}= & \{n-1,n+1\}.<br />
\end{split}<br />
\]

Mamy więc $ n $ różnych liczb $ r_1, \ldots,r_n $ rozmieszczonych w sumie $ n- 1 $ zbiorów $ A_1,\ldots ,A_{n-1} $. Co najmniej dwie z nich należą do tego samego zbioru $ A_l $, na mocy zasady szufladkowej. Ich suma równa się $ r_i+r_j=2n $. To znaczy, że suma $ k_i + k_j $ dzieli się przez $ 2n $; teza zachodzi i w tym przypadku.

Komentarze

Dodaj nową odpowiedź