LX OM - I - Zadanie 2

Dana jest liczba całkowita $ n \geq 2 $. Niech $ r_1, r_2, r_3, \cdots, r_{n-1} $ będą odpowiednio
resztami z dzielenia liczb

\[<br /> 1, 1+2, 1+2+3, \cdots, 1+2+ \cdots +(n-1)<br /> \]

przez $ n $. Znaleźć wszystkie takie wartości $ n $, że ciąg $ (r_1,r_2,\cdots,r_{n-1}) $ jest permutacją
ciągu $ (1, 2, \cdots,n-1) $.

Rozwiązanie

Odpowiedź: $ n =2^k $ dla $ k =1,2,3,\cdots $.

Wykażemy najpierw, że potęgi dwójki spełniają warunki zadania.
W tym celu wystarczy udowodnić, że jeżeli $ n =2^k $ dla pewnego całkowitego $ k \geq 1 $, to reszty
$ r_1, r_2, r_3, \cdots, r_n-1 $ są parami różne i żadna z nich nie jest równa zeru. Gdyby któraś z
tych reszt, powiedzmy $ r_m $, była równa zeru, to liczba

\[<br /> 1+2+\cdots+m = \frac{m(m+1)}{2}<br /> \]

byłaby podzielna przez $ 2^kk $. Zatem dla pewnej wartości $ m \in \{1,2, \cdots,2k - 1\} $ iloczyn
$ m(m+1) $ byłby podzielny przez $ 2^{k+1} $. Lecz jedna z liczb $ m $, $ m+1 $ jest
parzysta, a druga — nieparzysta. Stąd jedna z nich musiałaby być podzielna przez $ 2^{k+1} $,
wbrew temu, że obie te dodatnie liczby nie przekraczają $ 2^k $ . Gdyby z kolei dwie z rozważanych
reszt były równe — powiedzmy $ r_l = r_m $, gdzie $ 1 \leq l< m \leq n-1 $, wówczas liczba

\[<br /> (1+2+\cdots+m) - (1+2+\cdots+l) = \frac{m(m+1)}{2} - \frac{l(l+1)}{2} = \frac{(m-l)(m+l+1)}{2}<br /> \]

byłaby podzielna przez $ 2^k $, a więc iloczyn $ (m -l)(m+l +1) $ byłby podzielny przez $ 2^{k+1} $.
Suma tych czynników wynosi $ 2^{m+1} $, jest więc liczbą nieparzystą. Tak jak wcześniej wynika stąd,
że jedna z liczb $ m - l $, $ m + l + 1 $ musi być podzielna przez $ 2^{k+1} $ . Jednakże liczby $ l $ i $ m $
są różne, dodatnie i mniejsze od $ 2^k $, i podobnie jak poprzednio otrzymujemy sprzeczność.

Aby dokończyć rozwiązanie zadania, wystarczy dowieść, że gdy liczba $ n $ ma nieparzysty dzielnik pierwszy $ p $,
to ciąg $ (r_1,r_2,\cdots,r_{n-1}) $ nie jest permutacją ciągu $ (1,2,\cdots,n - 1) $. Zauważmy w tym celu, że
dla dowolnej liczby całkowitej dodatniej $ t $ liczby

\[<br /> 1+2+...+(tp-2)+(tp-1) = \frac{tp(tp-1)}{2},<br /> \]
\[<br /> 1+2+...+(tp-1)+tp = \frac{tp(tp+1)}{2}<br /> \]

są podzielne przez p, gdyż nieparzysty czynnik pierwszy p w liczniku nie skraca się z mianownikiem.
W związku z tym reszty

\[<br /> r_{p-1},r_p,r_{2p-1},r_{2p},r_{3p-1},r_{3p}, \cdots, r_{n-p-1},<br /> r_{n-p},r_{n-1}<br /> \]

są podzielne przez p. Zatem w ciągu $ (r_1,r_2,\cdots,r_{n-1}) $ co
najmniej $ 2\cdot \frac{n}{p}-1 $ liczb jest podzielnych przez $ p $.
W ciągu (1,2, \cdots,n-1) występuje zaś jedynie $ n-1 $ liczb podzielnych
przez $ p $. Tak więc liczba $ n $ nie ma żądanej własności

.

Komentarze

Dodaj nową odpowiedź