LV OM - III - Zadanie 6

Zawody matematyczne:

LV OM, 2003-2004

Etap:

III

Dana jest liczba całkowita $m> 1$ . Nieskończony ciąg liczb całkowitych $x_0,x_1,x_2,\ldots$ jest określony przez warunki

$ x_{i}=\left\{\begin{array}{ll} 2^{i}&\textrm{dla}\ i<m,\\ x_{i-1}+x_{i-2}+\ldots+x_{i-m}&\textrm{dla}\ i \geq m. \end{array}\right. $

Wyznaczyć największą liczbę naturalną $k$ , dla której istnieje $k$ kolejnych wyrazów tego ciągu podzielnych przez $m$ .

Rozwiązanie

Wzór rekurencyjny

$ (1) \quad x_{i}-x_{i-1}-x_{i-2}-\ldots-x_{i-m}=0\ \textrm{dla}\ i \geq m $

działa zarówno do przodu, jak i do tyłu; to znaczy, że każdy odcinek $m$ kolejnych wyrazów ciągu $(x_i)$ wyznacza zarówno wszystkie wyrazy późniejsze, jak i wszystkie wyrazy wcześniejsze. Ta sama uwaga odnosi się też do ciągu $r_0,r_1 ,r_2,\ldots,$ gdzie $r_i$ jest resztą z dzielenia $x_i$ przez $m$ ; wzór (1) implikuje wzór

$ (2) \qquad r_i - r_{i-1} - r_{i-2} -\ldots - r_{i-m} \equiv 0 \ (\mathrm{mod}\ m) \ \textrm{dla}\ i \geq m. $

W ciągu $(r_i)$ każdy odcinek długości $m$ jest układem złożonym z $m$ liczb ze zbioru $\{0,1,\ldots,m-1\}$ . Ponieważ jest tylko skończenie wiele takich układów, muszą się one powtarzać: istnieją numery $s,t$ ( $s < t$ ) takie, że

$ (r_t, r_{t+1},r_{t+2},\ldots,r_{t+m-1}) = (r_s, r_{s+1}, r_{s+2},\ldots, r_{s+m-1}). $

Każdy z tych dwóch odcinków ciągu $(r_i)$ jednoznacznie wyznacza wyraz bezpośrednio go poprzedzający; na mocy wzoru (2) te wyrazy też są równe: $r_{t-1} = r_{s-1}$ . Zatem

$ (r_{t-1}, r_t, r_{t+1},\ldots,r_{t+m-2}) = (r_{s-1}, r_{s}, r_{s+1},\ldots, r_{s+m-2}). $

Cofając się w ten sposób dojdziemy do odcinka identycznego z odcinkiem początkowym:

$ (r_d, r_{d+1},r_{d+2},\ldots,r_{d+m-1}) = (r_0, r_{1}, r_{2},\ldots, r_{m-1}). $

gdzie $d = t - s$ . Tak więc

$ r_d = 1,\ r_{d+1} = 2,\ r_{d+2} = 4,\ldots ,\ r_{d+m-1} = (2^{m-1} \mathrm{mod}\ m). $

Cofając się dalej, zgodnie ze wzorem (2), stwierdzamy kolejno, że

$ r_{d-1} = 1,\ r_{d-2} = 0, r_{d-3} = 0, \ldots,\ r_{d-m} = 0, $

i mamy $m - 1$ kolejnych wyrazów $x_{d-m}, \ldots , x_{d-2}$ podzielnych przez $m$ .

Oczywiście nie istnieje $m$ kolejnych wyrazów $x_i$ podzielnych przez $m$ , bo wówczas, w myśl wzoru (1), cały ciąg $(x_i)$ składałby się z liczb podzielnych przez $m$ , wbrew temu, że $x_0 = 1$ . Zatem szukana maksymalna wartość $k$ wynosi $m - 1$ .