LX OM - I - Zadanie 12

Dana jest liczba pierwsza $ p $. Po lewej stronie tablicy napisano liczby $ 1, 2, 3, \cdots, p - 1 $,
zaś po prawej stronie liczbę $ 0 $. Wykonujemy ciąg $ p - 1 $ ruchów, z których każdy przebiega
następująco: Wybieramy jedną z liczb napisanych po lewej stronie tablicy, dodajemy ją do wszystkich
pozostałych liczb na tablicy, po czym wymazujemy wybraną liczbę.

Rozstrzygnąć, dla jakich wartości
$ p $ można w kolejnych ruchach wybierać liczby w taki sposób, by liczba pozostała na tablicy po
wykonaniu wszystkich ruchów była podzielna przez p.

Rozwiązanie

Odpowiedź: Dla wszystkich liczb pierwszych p oprócz 2 i 3.

Niech $ t_i $ dla $ i=1,2, \cdots,p-1 $ oznacza początkową wartość tej liczby, która
została wymazana z tablicy w $ i $-tym ruchu. Zatem ciąg $ (t_1,t_2,t_3 ...,t_{p-1}) $ jest permutacją
ciągu $ (1,2,3, \cdots,p-1) $ oraz jednoznacznie określa sposób wyboru zmazywanych liczb w kolejnych ruchach.

Wprowadźmy oznaczenie

\[<br /> s_i = t_i +2t_{i-1} +4t_{i-2} + \cdots +2^{i-2}t_2 +2^{i-1}t_1 \quad \text{dla } i=1,2, \cdots,p-1.<br /> \]

Wykażemy indukcyjnie, że po wykonaniu $ i $-tego ruchu wszystkie liczby na tablicy są większe
o $ s_i $ od swych początkowych wartości.

Istotnie: stwierdzenie to jest prawdą dla $ i = 1 $, gdyż w pierwszym ruchu wymazano liczbę
$ t_1 $, zwiększając uprzednio wszystkie pozostałe liczby o $ s_1 = t_1 $. Jeżeli natomiast po
wykonaniu $ i $-tego ruchu wszystkie liczby na tablicy były większe o $ s_i $ od początkowych wartości,
to w szczególności liczba początkowo równa $ t_{i+1} $ po wykonaniu $ i $-tego ruchu miała wartość
$ t_{i+1} + s_i $. Wobec tego w wyniku $ (i+1) $-szego ruchu dodano do wszystkich pozostałych liczb wielkość
$ t_{i+1} + s_i $. Ponieważ zaś liczby te po $ i $-tym ruchu były większe o $ s_i $ od początkowych wartości,
więc po $ (i+1) $-szym ruchu stały się one większe o $ t_{i+1}+s_i+s_i $ od swych początkowych wartości.
Pozostaje spostrzec, że

\[<br /> \begin{split}<br /> t_{i+1}+2s_i &= t_{i+1}+2(t_i +2t_{i-1} +4t_{i-2}+ \cdots +2^{i-2}t_2 +2^{i-1}t_1)=\\<br /> &= t_{i+1} +2t+i +4t_{i-1} +8t_{i-2} + ...+2^{i-1}t_2 +2^it_1 = \\<br /> &= s_{i+1},<br /> \end{split}<br /> \]

co kończy dowód indukcyjny. Udowodniliśmy tym samym, że po wykonaniu wszystkich $ p $ ruchów liczba
pozostała po prawej stronie tablicy wynosi

\[<br /> (1) \qquad t_{p-1} +2t_{p-2} +4t_{p-3} + \cdots +2^{p-3}t_2 +2^{p-2}t_1.<br /> \]

Sprowadziliśmy zatem zadanie do wyznaczenia wszystkich liczb pierwszych $ p $, dla których istnieje taka permutacja
$ (t_1,t_2,t_3, \cdots,t_{p-1}) $ ciągu $ (1,2,3, \cdots,p-1) $, że liczba (1) jest podzielna przez $ p $.

Bezpośrednio sprawdzamy, że dla $ p=2 $ i $ p=3 $ nie jest możliwe otrzymanie liczby podzielnej przez $ p $:
dla $ p = 2 $ liczba (1) wynosi $ 1 $, a dla $ p = 3 $ może ona być równa $ 1+2\cdot 2=5 $ albo $ 2+2\cdot 1 = 4 $.

Wykażemy, że jeśli $ p $ jest liczbą pierwszą większą od $ 3 $, to dla permutacji

\[<br /> (2) \qquad (t_1,t_2,t_3,t_4, \cdots,t_{p-2},t_{p-1})=(p-2,p -1,p-4,p-3, \cdots, 5,6,3,4,2, 1),<br /> \]

powstałej z ciągu $ (1,2,3,4, \cdots,p - 2,p - 1) $ przez zamianę miejsc w parach $ (2j-1,2j) $ dla
$ j \geqslant 2 $ i następnie odwrócenie kolejności, liczba (1) jest podzielna przez $ p $.

Rzeczywiście, dla permutacji (2) liczba (1) ma wartość

\[<br /> L =1+2\cdot 2+2^2 \cdot4+2^3 \cdot 3 + 2^4 \cdot 6+2^5 \cdot 5+ \cdots +2^{p-3}(p-1)+2^{p-2}(p-2).<br /> \]

Dla $ j =2,3, \cdots, \frac{1}{}2(p-1) $ prawdziwa jest zależność

\[<br /> \begin{split}<br /> 2^{2j-2}\cdot 2j +2^{2j-1}(2j -1) &= 2^{2j-2}(2j -1)+2^{2j-1} \cdot 2j +2^{2j-2} -2^{2j-1} =\\<br /> &= 2^{2j-2}(2j -1)+2^{2j-1}\cdot 2j -2^{2j-2},<br /> \end{split}<br /> \]

z której wynika, że $ L = M - N $, gdzie $ M $ jest sumą liczb postaci $ 2^{i-1}i $ dla
$ i =1,2, \cdots,p-1 $, natomiast $ N =2^2 +2^4 +2^6 + \cdots +2^{p-3} $. Korzystając ze wzoru na sumę kolejnych
wyrazów ciągu geometrycznego obliczamy, że

\[<br /> \begin{split}<br /> M &= (2^0 + ...+2^{p-2})+(2^1 + \cdots +2^{p-2})+ \cdots +(2^{p-3} +2^{p-2})+2^{p-2} = \\<br /> &= 2^0(2^{p-1} -1)+2^1(2^{p-2} -1)+ \cdots+2^{p-3}(2^2 -1)+2^{p-2}(2^1 -1) = \\<br /> &= (p-1)2^{p-1} -(2^0 +2^1 + \cdots +2^{p-3} +2^{p-2})= \\<br /> &= (p-1)2^{p-1} -(2^{p-1} -1) = \\<br /> &= p\cdot 2^{p-1} -2\cdot 2^{p-1} +1 \\<br /> \end{split}<br /> \]

oraz

\[<br /> N=2^2(4^0+4^1+\cdots 4^{\frac{p-7}{2}}+4^{\frac{p-5}{2}}) = 2^2\cdot \frac{4^{\frac{p-3}{2}}}{3}<br /> =2^2\cdot \frac{2^{p-3}-1}{3} = \frac{2^{p-1}-4}{3}.<br /> \]

W efekcie

\[<br /> (3) \qquad L=M-N = p\cdot 2^{p-1}+\frac{-6\cdot 2^{p-1}+3-2^{p-1}+4}{3} = p\cdot 2^{p-1} - \frac{7(2^{p-1}-1)}{3}.<br /> \]

Na mocy małego twierdzenia Fermata (zob. LI Olimpiada Matematyczna, Sprawozdanie Komitetu Głównego,
Warszawa 2001, Dodatek A, str. 102) liczba $ 2^{p-1} -1 $ jest podzielna przez $ p $. Skoro zaś $ p $
jest liczbą pierwszą większą od $ 3 $, ułamek występujący po prawej stronie zależności (3) jest liczbą
podzielną przez $ p $. Zatem prawa strona tej zależności jest liczbą podzielną przez $ p $, co kończy
rozwiązanie zadania.

Komentarze

Dodaj nową odpowiedź