XXXVI OM - II - Zadanie 5

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

\[<br />
a_i = \left\{<br />
\begin{array}{rl}<br />
i & \textrm{dla} \ i \ \textrm{nieparzystych}\\<br />
n-i & \textrm{dla} \ i \  \textrm{parzystych}\\<br />
0 & \textrm{dla} i=0<br />
\end{array}<br />
\right.<br />
\]

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

\[<br />
\begin{split}<br />
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 =\\<br />
= (1+3+ \ldots + (2j-1))+((n-2) + (n-4)+ \ldots + (n-2j)) = \\<br />
= (1+2+3+4+ \ldots + (2j-1) + 2j)-4(1+2+\ldots +j)+jn =\\<br />
 = j (2j+1)-2j (j+1) +jn =jn-j<br />
\end{split}<br />
\]

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

\[<br />
b_{2j+1} = b_{2j} + a_{2j + 1} =jn-j + 2j+1  =jn+j+1.<br />
\]

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

Komentarze

błąd

w punkcie b) powinno być "n-1" zamiast "n|1"

Dodaj nową odpowiedź