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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź