Consideram sirul (Xn)n definit prin relatia Xn+2=|Xn+1-Xn-1| pentru n>=1, cu termenii X0, X1,X2 naturali,nu toti 3 nuli.Sa se demonstreze ca sirul (Xn)n e periodic de la un rang incolo si sa se determine perioada sirului.
Am nontat modulul cu | | iar n+1 ,n-1 etc sunt indicii lui X.
PS:deadline-ul pentru trimiterea problemelor din GMB 10 este 28 februarie.

Din pacate am pierdut dupa reboot cele scrise,
in principiu era cam acelasi text scris in latex,
in acest mod se vedea imediat care e problema si macar care e inceputul.

Observatia care rezolva o mare parte din neplaceri este urmatoarea.
Sirul dat pleaca cu trei termeni, a,b,c in notatia mea provizorie.
(Urasc x0, x1, x2 cand trebuie sa tiparesc asa ceva mai des.)

Avem de-a face cu numere naturale intre 0 si M = max(a,b,c) pentru primii trei termeni ai sirului, dar din cauza modului in care e definit recursiv sirul si termenii care vin au aceleasi calitati.

In particular avem un numar finit de posibilitati pentru "trei termeni consecutivi" ai sirului. De aici rezulta periodicitatea. (Recursiunea este una de ordin trei.)

Pentru a vedea / a intrezari care este perioada, propun sa facem ceea ce recomand mereu sa facem. Experimentam!

In acest secol, a scrie cod este un mod util de a ne crea exemple.
Iata deci cam ce exemple obtinem plecan cau cateva numere aleatoare...

COD:


Una din rulari mi-a produs:
Rezultate:


(Desigur ca daca incepem cu 0,0,0 dam de alta perioada, dar problema a exclus acest caz.)

Sa incercam acum impreuna...

Nota:
Care este exact sursa problemei, pagina si autorul mai ales. (Nu am Gazeta si nu o voi avea.)

deci cam stim ca perioada e de 7 elemente,si ar trebui sa incercam sa demonstram asta?


Pagina 479 problema 26819 autor domnul Ion Ciudin ,Botosani

[Citat] deci cam stim ca perioada e de 7 elemente si ar trebui sa incercam sa demonstram asta?

Da.
Important este insa pentru inceput sa facem cateva observatii (in plus).
Observatia ca perioada este / poate fi 7 este una pe care se acorda cateva puncte in concurs. Cum putem face mai mult(e puncte)?

[Citat] Important este insa pentru inceput sa facem cateva observatii (in plus). Observatia ca perioada este / poate fi 7 este una pe care se acorda cateva puncte in concurs. Cum putem face mai mult(e puncte)?

In general presupunem ca nu e periodic si cautam contradictia(de forma generala).

[Citat] In general presupunem ca nu e periodic si cautam contradictia(de forma generala).

Considerente de logica nu pot rezolva (singure) problema.
Fara observatii asupra sirurilor construite experimental nu vad cum putem rezolva problema pana la capat.

Partea cu periodicitatea am explicat-o deja.
Sirul dat este definitiv periodic. Motivul: Sirul este marginit, de numere naturale, deci ia o multime finita de valori. Deoarece avem o recurenta de ordin trei rezulta periodicitatea. Este clar cum?

Daca nu, rog a se incerca intai clarificarea argumentului de mai sus.
Daca da, o rafinare a argumentului deschide drumul spre solutie.

[Citat] Daca da, o rafinare a argumentului deschide drumul spre solutie.

Ar?ta?i-ne cum, v? rog.

[Citat] Daca da, o rafinare a argumentului deschide drumul spre solutie.

M-am referit la faptul ca relatia de recurenta genereaza la fiecare pas elemente mai mici sau egale decat cele (doua) folosite.

Sirul este periodic.
Consideram valoarea maxima din perioada. Notam aceasta valoare cu a.
Ea apare candva, consideram si urmatorii termeni, b si c in notatie.

In primul rand observam ca nu putem avea trei valori diferite intre valorile a,b,c. Altfel, a > b si a > c. Urmatorul termen al sirului este a-c .
Dar daca ne uitam la
a, b, c, a-c, ...
intre ultimele trei numere mentionate inca trebuie sa mentinem maximul a, altfel acesta nu mai revine. Deci a-c = a, deci c = 0 .
Sirul este atunci ... , a, b, 0, a, a-b, a-b, b si in ultimii trei termeni am pierdut maximumul a, contradictie.

Consideram acum cele patru cazuri posibile
(1) a,a,a
(2) a,a,b
(3) a,b,a
(4) a,b,b
in care intre a,b,c avem cel mult doua valori diferite, cu valoarea maxima a pe primul loc si cu b, daca apare (ultimele trei cazuri), avand o valoare b < a .

Pe rand:
(1) a,a,a, 0,a,0,0,a,a,a,... si deja avem perioada.

(2) a,a,b, a-b,b si deja maximul scade strict sub a daca b este nenul, contradictie. Deci b=0, plecam cu a,a,0, secventa pe care o vedem in (1), deci obtinem aceeasi perioada.

(3) a,b,a, 0,b,a-b si deja maximul scade strict sub a daca b este nenul, contradictie. Deci b=0, plecam cu a,0,a, secventa pe care o vedem in (1).

(4) a,b,b, a-b si deja maximul scade strict sub a daca b este nenul, contradictie. Deci b=0, plecam cu a,0,0, secventa pe care o vedem in (1).

Trebuie sa mai mentionam ca nu putem avea a=0, caz in care perioada ar fi mai mica. (Ne uitam la ultimul termen al sirului care este nenul pentru a da de o contradictie.)

Frumos.
Apropo de aceast? problem?, una propus? în Kvant în 1976 sun? a?a:

Am inteles demosntratia, foarte frumoasa. Acum mai ramane de demonstarat ca perioada e constanta,(cred ca daca artam ca e constatnta e suficient sa dam exemplu un sir dintre cele de mai sus pt a vedea ca e 7)