ciag fibonacciego

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
bar03
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 21 lis 2011, o 00:51
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 1 raz

ciag fibonacciego

Post autor: bar03 »

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.
Awatar użytkownika
Vax
Użytkownik
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

Post autor: Vax »

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.
bar03
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 21 lis 2011, o 00:51
Płeć: Mężczyzna
Lokalizacja: Radom
Podziękował: 1 raz

ciag fibonacciego

Post autor: bar03 »

Niezły gośc z Ciebie. Tak z ciekawości sam wpadłeś na ten dowód?
ODPOWIEDZ