XLIII OM - I - Zadanie 9

Zawody matematyczne:

XLIII OM, 1991-1992

Etap:

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:

$ r_i = r_j \quad \textrm{dla pewnych} \quad i,j,\ i \ne j. $

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

$ \{1,\ldots,n-1\} \cup \{n+1,\ldots,2n-1\}. $

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

$ \begin{split} A_1 = & \{1, 2n - 1\}, \\ A_2 = & \{2,2n-2\}, \\ \vdots \\ A_{n-1}= & \{n-1,n+1\}. \end{split} $

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.