Matematyka.pl

Uzasadnij że dwie ostatnie cyfry ciągu Fibonacciego tworzą ciąg okresowy, Znajdź ten okres.

Pytałem już chyba wszystkich znajomych i nikt nie potrafił mi pomóc. Liczę, że uda się to jakiemuś geniuszowi policzyć .

Istnieje alternatywne zadanie dotyczące 1 cyfry po przecinku. Otóż wtedy okres ma aż 60 liczb w rozwinięciu : 01123535831453497077415617853819099875279651673033695493257291 (o ile się nie pomyliłem przy przepisywaniu z kartki).
Mogę tylko zasugerować, aby okres liczyć np. w systemie 2-kowym, lub 5-tkowym, a nie 10-kowym

Proszę, aby ktoś to rozwiązał do końca. Nawet w tym innym systemie .

01123581321345589443377108797848165461157682593181129406997887655217698655419
63733703737649257499737245176279412061814223658853419435296493575075764218569
19788857358318920929386757277492675176775330831396951419335285372259814021618
24325689361541569845337902717446156671378455398514904949984745923729669561561
77390635316698554399332255782392160814122638548338114959413173047772412526517
72853338719808969582785129796152136579350439336296594595312657742196180412162
83452873174754924739770673744145863117486513789169602989187253257894635811697
13102333568945347913925972991

tak wygląda okres tego ciągu

Cóż, chodzi tu o wyznaczenie okresu ciągu liczb Fibonacciego \(\displaystyle{ \pmod{100}}\). To zadanie jest dość proste, jeśli zna się podstawy teorii grup i zauważy się, że:

a) Kolejne liczby ciągu fibonacciego da się wygenerować, podnosząc do kolejnych potęg macierz \(\displaystyle{ \begin{bmatrix} 1 1 \\ 0 1 \end{bmatrix}}\) (po pomnożeniu jej przez wektor \(\displaystyle{ [1,1]}\)).

b) Macierze dwuelementowe o niezerowym wyznaczniku, brane mod dowolne n, tworzą multiplikatywną grupę

Teraz wystarczy znaleźć rząd ww. macierzy, a mając rząd ww. grupy jest to sprawdzenie jakichś stu przypadków, co przy pomocy komputera jest dość szybkie

Czy tego zadania nie da się rozwiązać w jakiś postrzy sposób??

Można też myśleć tak: jeśli mamy dane dwie ostatnie cyfry dwóch kolejnych wyrazów ciągu Fibonacciego, to jednoznacznie dane są dwie ostatnie cyfry następnego wyrazu. Ponieważ jest \(\displaystyle{ 10 \; 000}\) możliwych par >par dwóch ostatnich cyfr< dwóch kolejnych wyrazów, zatem z ZSD wynika, że w końcu ciąg się zapętli i pary ostatnich cyfr zaczną się powtarzać. Znaleźć okres chyba trzeba ręcznie. ;-/

zatem z ZSD wynika, że w końcu ciąg się zapętli i pary ostatnich cyfr zaczną się powtarzać

Nie widzę tego. To, że się powtórzą, jest oczywiste, ale nie widzę powodu, aby ZSD wymuszało na nich powtarzanie się cykliczne.

Cykliczność wynika ze wcześniej wspomnianego determinizmu:

mamy dwie kolejne dwucyfrówki \(\displaystyle{ \Rightarrow}\) mamy następną (jednoznacznie)

A to z tym się już w zupełności zgodzę.

Sprawdziłem sobie długość okresu jeśli zamiast wyrazów początkowych 1 i 1 podstawimy co innego. Okres jest równy 300 (tak jak tu) lub krótszy i jest dzielnikiem 300. (Sprawdzałem dla wyrazów początkowych \(\displaystyle{ a,b}\) gdzie \(\displaystyle{ a,b\in \{0,1,2,...,99\}}\)). Czyli można podejrzewać, że to 300 wynika z jakiś mądrych rzeczy