XXXVI OM - II - Zadanie 5

Zawody matematyczne:

XXXVI OM, 1984-1985

Etap:

Udowodnić, że dla liczby naturalnej $n$ większej od 1 następujące warunki są równoważne:

a) $n$ jest liczbą parzystą,

b) istnieje permutacja $(a_0, a_1, a_2, \ldots, a_{n-1})$ zbioru $\{0,1,2,\ldots,n—1\}$ o tej własności, że ciąg reszt z dzielenia przez $n$ liczb $a_0, a_0 + a_1, a_0 + a_1 + a_2, \ldots, a_0 + a_1 + a_2 +\ldots a_{n-1}$ jest też permutacją tego zbioru.

Rozwiązanie

Dowodzimy, że z warunku a) wynika warunek b). Zakładamy, że $n$ jest liczbą parzystą i przyjmujemy

$ a_i = \left\{ \begin{array}{rl} i & \textrm{dla} \ i \ \textrm{nieparzystych}\\ n-i & \textrm{dla} \ i \ \textrm{parzystych}\\ 0 & \textrm{dla} i=0 \end{array} \right. $

Niech $b_k=a_0+a_1+\ldots+a_k$ dla $k = 0,1,\ldots,n-1$ . Wówczas dla $j<n$ zachodzą równości

$ \begin{split} b_{2j}=\sum_{i \leq 2j} a_i = \sum_{\substack{i \leq 2j \\ i \textrm{nieparzyste}}} a_i + \sum_{\substack{i \leq 2j \\ i \textrm{parzyste}}} a_i =\\ = (1+3+ \ldots + (2j-1))+((n-2) + (n-4)+ \ldots + (n-2j)) = \\ = (1+2+3+4+ \ldots + (2j-1) + 2j)-4(1+2+\ldots +j)+jn =\\ = j (2j+1)-2j (j+1) +jn =jn-j \end{split} $

(również dla $j = 0$ ) oraz

$ b_{2j+1} = b_{2j} + a_{2j + 1} =jn-j + 2j+1 =jn+j+1. $

Zatem przy dzieleniu przez $n$ :

$b_0$ daje resztę $0$
$b_{2j}$ daje resztę $n-j \left( j = 1,\ldots, \frac{n}{2} -1 \right)$
$b_{2j+1}$ daje resztę $j+1 \left( j = 0,\ldots, \frac{n}{2} -1 \right)$ .

Otrzymane reszty wyczerpują cały zbiór $\{0,1,2,\ldots,n-1\}$ , czyli określona przez nas permutacja $(a_0,\ldots,a_{n-1})$ ma żądaną własność.

Przechodzimy do dowodu, że z warunku b) wynika warunek a).

Załóżmy, że istnieje permutacja $(a_0,\ldots,a_{n-1})$ zbioru $\{0,\ldots,n-1\}$ o własności podanej w warunku b) i oznaczmy, jak w poprzedniej części dowodu, $b_k = a_0+ \ldots +a_k$ dla $k = 0,1,\ldots,n- 1$ . Jeśli $a_0 \ne 0$ , to musi być $a_j = 0$ dla pewnego $j \geq 1$ i wówczas $b_j = b_{j-1}+a_j = b_{j-1}$ wbrew założeniu, źe reszty liczb $b_k$ z dzielenia przez $n$ są wszystkie różne. Zatem $a_0 = 0$ , więc i $b_0 = 0$ . Wobec tego żadna z liczb $b_1,\ldots,b_{n-1}$ nie może dać przy dzieleniu przez $n$ reszty $0$ , czyli nie może dzielić się przez $n$ . Ale $b_{n-1} =\sum_{i=0}^{n-1} a_i = \sum_{i=0}^{n-1} a_i = \sum_{i=0}^{n-1} i$ (bo ciąg $(a_0,\ldots,a_{n-1})$ jest permutacją zbioru $\{0,\ldots,n- 1\}$ ), a ta ostatnia suma równa się $n(n-1)/2$ . Skoro więc $b_{n-1}$ nie dzieli się przez $n$ , to czynnik $(n-1)/2$ nie jest liczbą całkowitą, a to znaczy, że $n$ jest liczbą parzystą.