LV OM - III - Zadanie 6

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

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

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

\[<br />
(1) \quad x_{i}-x_{i-1}-x_{i-2}-\ldots-x_{i-m}=0\ \textrm{dla}\ i \geq m<br />
\]

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

\[<br />
(2) \qquad r_i - r_{i-1} - r_{i-2} -\ldots - r_{i-m} \equiv 0 \  (\mathrm{mod}\ m) \  \textrm{dla}\ i \geq m.<br />
\]

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

\[<br />
(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}).<br />
\]

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

\[<br />
(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}).<br />
\]

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

\[<br />
(r_d, r_{d+1},r_{d+2},\ldots,r_{d+m-1}) = (r_0, r_{1}, r_{2},\ldots, r_{m-1}).<br />
\]

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

\[<br />
r_d = 1,\ r_{d+1} = 2,\ r_{d+2} = 4,\ldots ,\ r_{d+m-1} = (2^{m-1} \mathrm{mod}\  m).<br />
\]

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

\[<br />
r_{d-1} = 1,\ r_{d-2} = 0, r_{d-3} = 0, \ldots,\ r_{d-m} = 0,<br />
\]

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

Komentarze

Dodaj nową odpowiedź