Ciąg Fibonacciego - zadanie nie jest proste ;)

[unikat900]

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

[KoMBiNaT]

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

[unikat900]

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

[Szemek]

01123581321345589443377108797848165461157682593181129406997887655217698655419
63733703737649257499737245176279412061814223658853419435296493575075764218569
19788857358318920929386757277492675176775330831396951419335285372259814021618
24325689361541569845337902717446156671378455398514904949984745923729669561561
77390635316698554399332255782392160814122638548338114959413173047772412526517
72853338719808969582785129796152136579350439336296594595312657742196180412162
83452873174754924739770673744145863117486513789169602989187253257894635811697
13102333568945347913925972991

tak wygląda okres tego ciągu

[L_b]

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

[KasienkaG]

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

[Dasio11]

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. ;-/

[Althorion]

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.

[Dasio11]

Cykliczność wynika ze wcześniej wspomnianego determinizmu:

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

[Althorion]

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

[abc666]

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