Wykaż, że wśród początkowych \(\displaystyle{ 10^{8} +1}\) wyrazów ciągu Fibonacciego istnieje taki, którego zapis dziesiętny kończy się czterema zerami.
Wszelkie wskazówki mile widziane.
ciag fibonacciego
- Vax
- Użytkownik
- Posty: 2913
- Rejestracja: 27 kwie 2010, o 22:07
- Płeć: Mężczyzna
- Lokalizacja: Biała Podlaska / Warszawa
- Podziękował: 4 razy
- Pomógł: 612 razy
ciag fibonacciego
Niech \(\displaystyle{ F_0,F_1,F_2,...}\) będą kolejnymi wyrazami ciągu Fibonacciego i niech \(\displaystyle{ F_0 = 0}\), zdefiniujmy również ciąg:
\(\displaystyle{ a_k = F_k \pmod{10^4} , 0 \le k \le 10^8}\)
Załóżmy nie wprost, że żaden spośród \(\displaystyle{ 10^8+1}\) kolejnych początkowych wyrazów ciągu Fibonacciego nie przystaje do 0 modulo \(\displaystyle{ 10^4}\), wtedy każdy wyraz ciągu \(\displaystyle{ a_k}\) może przyjmować wartości ze zbioru \(\displaystyle{ \lbrace 1;2;3;...;10^4-1\rbrace}\), jest ich łącznie \(\displaystyle{ 10^4-1}\).
Pokażę teraz, że wśród \(\displaystyle{ 10^8+1}\) początkowych wyrazów ciągu Fibonacciego co najmniej jedna para \(\displaystyle{ (a_n,a_{n+1})}\) się powtórzy. Popatrzmy na pary \(\displaystyle{ (a_0,a_1)}\), \(\displaystyle{ (a_1,a_2)}\), ... , \(\displaystyle{ (a_{10^8-1},a_{10^8})}\)
Takich par jest \(\displaystyle{ 10^8}\), jednak dwuwyrazowych wariacji z powtórzeniami ze zbioru \(\displaystyle{ 10^4-1}\) elementowego jest \(\displaystyle{ (10^4-1)^2 < 10^8}\), skąd na mocy zasady szufladkowej Dirichleta muszą istnieć co najmniej 2 takie same pary, niech to będą \(\displaystyle{ (a_n,a_{n+1})}\) oraz \(\displaystyle{ (a_m,a_{m+1})}\), gdzie \(\displaystyle{ m>n}\) czyli:
\(\displaystyle{ \begin{cases} a_{n+1}=a_{m+1}\\ a_n = a_m \end{cases}}\)
Odejmując stronami dostajemy kolejno:
\(\displaystyle{ a_{n-1} = a_{m-1}}\)
\(\displaystyle{ a_{n-2} = a_{m-2}}\)
...
\(\displaystyle{ a_0 = a_{m-n}}\)
Ale \(\displaystyle{ a_0=0}\) więc \(\displaystyle{ a_{m-n} = 0}\) czyli \(\displaystyle{ F_{m-n} \equiv 0 \pmod{10^4}}\), stąd sprzeczność (bo \(\displaystyle{ m-n \le 10^8}\)) która dowodzi, że wśród \(\displaystyle{ 10^8+1}\) początkowych wyrazów ciągu Fibonacciego zawsze znajdzie się pewien wyraz (\(\displaystyle{ F_{m-n}}\)) mający na końcu 4 zera, cnd.
\(\displaystyle{ a_k = F_k \pmod{10^4} , 0 \le k \le 10^8}\)
Załóżmy nie wprost, że żaden spośród \(\displaystyle{ 10^8+1}\) kolejnych początkowych wyrazów ciągu Fibonacciego nie przystaje do 0 modulo \(\displaystyle{ 10^4}\), wtedy każdy wyraz ciągu \(\displaystyle{ a_k}\) może przyjmować wartości ze zbioru \(\displaystyle{ \lbrace 1;2;3;...;10^4-1\rbrace}\), jest ich łącznie \(\displaystyle{ 10^4-1}\).
Pokażę teraz, że wśród \(\displaystyle{ 10^8+1}\) początkowych wyrazów ciągu Fibonacciego co najmniej jedna para \(\displaystyle{ (a_n,a_{n+1})}\) się powtórzy. Popatrzmy na pary \(\displaystyle{ (a_0,a_1)}\), \(\displaystyle{ (a_1,a_2)}\), ... , \(\displaystyle{ (a_{10^8-1},a_{10^8})}\)
Takich par jest \(\displaystyle{ 10^8}\), jednak dwuwyrazowych wariacji z powtórzeniami ze zbioru \(\displaystyle{ 10^4-1}\) elementowego jest \(\displaystyle{ (10^4-1)^2 < 10^8}\), skąd na mocy zasady szufladkowej Dirichleta muszą istnieć co najmniej 2 takie same pary, niech to będą \(\displaystyle{ (a_n,a_{n+1})}\) oraz \(\displaystyle{ (a_m,a_{m+1})}\), gdzie \(\displaystyle{ m>n}\) czyli:
\(\displaystyle{ \begin{cases} a_{n+1}=a_{m+1}\\ a_n = a_m \end{cases}}\)
Odejmując stronami dostajemy kolejno:
\(\displaystyle{ a_{n-1} = a_{m-1}}\)
\(\displaystyle{ a_{n-2} = a_{m-2}}\)
...
\(\displaystyle{ a_0 = a_{m-n}}\)
Ale \(\displaystyle{ a_0=0}\) więc \(\displaystyle{ a_{m-n} = 0}\) czyli \(\displaystyle{ F_{m-n} \equiv 0 \pmod{10^4}}\), stąd sprzeczność (bo \(\displaystyle{ m-n \le 10^8}\)) która dowodzi, że wśród \(\displaystyle{ 10^8+1}\) początkowych wyrazów ciągu Fibonacciego zawsze znajdzie się pewien wyraz (\(\displaystyle{ F_{m-n}}\)) mający na końcu 4 zera, cnd.