XLIX OM - III - Zadanie 4

Zawody matematyczne:

XLIX OM, 1997-1998

Etap:

III

Dowieść, że w ciągu $(a_n)$ określonym wzorami

$ a_1 = 1, \quad a_n = a_{n-1} + a_{[n/2]}\ \textrm{dla}\ n = 2,3,4,\ldots $

występuje nieskończenie wiele liczb podzielnych przez $7$ .

Uwaga: $[n/2]$ jest największą liczbą całkowitą nie przekraczającą $n/2$ .

Rozwiązanie

W ciągu $(a_n)$ są wyrazy podzielne przez $7$ (na przykład $a_5 = 7$ ). Przypuśćmy, że jest ich skończenie wiele; niech $a_k$ będzie ostatnim z tych wyrazów. Oznaczmy: $a_k = x$ , $a_{2k-1} = y$ , $a_{4k-3} = z$ ; liczba $x$ dzieli się przez $7$ , a liczby $y$ i $z$ - nie.

Zachodzą równości:

$ \begin{array}{llllll} a_{2k}&=a_{2k-1}+a_{k}&=x+y,&a_{2k+1}&=a_{2k}+a_{k}&=2x+y,\\ a_{4k-2}&=a_{4k-3}+a_{2k-1}&=y+z,&a_{4k-1}&=a_{4k-2}+a_{2k-1}&=2y+z,\\ a_{4k}&=a_{4k-1}+a_{2k}&=x+3y+z,&a_{4k+1}&=a_{4k}+a_{2k}&=2x+4y+z,\\ a_{4k+2}&=a_{4k+1}+a_{2k+1}&=4x+5y+z,&a_{4k+3}&=a_{4k+2}+a_{2k+1}&=6x+6y+z,\\ \end{array} $

Przy dzieleniu przez $7$ liczby $a_{4k-3},a_{4k-2},\ldots,a_{4k+3}$ dają więc takie same reszty jak liczby $z, z + y, \ldots , z + 6y$ . Ponieważ $y$ nie dzieli się przez $7$ , wszystkie te reszty są różne. Zatem jedna z tych siedmiu liczb jest podzielna przez $7$ , wbrew przypuszczeniu, że $a_k$ jest ostatnim takim wyrazem. Sprzeczność kończy dowód.