Komentarz

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

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz