LX OM - I - Zadanie 12

Zawody matematyczne:

LX OM, 2008-2009

Etap:

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

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

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

$ \begin{split} 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)=\\ &= t_{i+1} +2t+i +4t_{i-1} +8t_{i-2} + ...+2^{i-1}t_2 +2^it_1 = \\ &= s_{i+1}, \end{split} $

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

$ (1) \qquad t_{p-1} +2t_{p-2} +4t_{p-3} + \cdots +2^{p-3}t_2 +2^{p-2}t_1. $

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

$ (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), $

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ść

$ 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). $

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

$ \begin{split} 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} =\\ &= 2^{2j-2}(2j -1)+2^{2j-1}\cdot 2j -2^{2j-2}, \end{split} $

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

$ \begin{split} M &= (2^0 + ...+2^{p-2})+(2^1 + \cdots +2^{p-2})+ \cdots +(2^{p-3} +2^{p-2})+2^{p-2} = \\ &= 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) = \\ &= (p-1)2^{p-1} -(2^0 +2^1 + \cdots +2^{p-3} +2^{p-2})= \\ &= (p-1)2^{p-1} -(2^{p-1} -1) = \\ &= p\cdot 2^{p-1} -2\cdot 2^{p-1} +1 \\ \end{split} $

oraz

$ 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} =2^2\cdot \frac{2^{p-3}-1}{3} = \frac{2^{p-1}-4}{3}. $

W efekcie

$ (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}. $

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.