Este gresit modul in care m-am gandit sa rezolv problema?

[Citat] Este gresit modul in care m-am gandit sa rezolv problema?

"Gresit" nu este cuvantul potrivit.
Pur si simplu este nevoie de strategia
(pana in ultimul detaliu care ne permite sa scriem pe aceasta baza un numar)
care numara exact ce se cere.

O sa incerc sa mai scriu propozitii, pentru a se vedea unde am eu probleme cu finalizarea ideii. Fac cat pot de mult pe aceasta directie.

Plecam cu trei cutii / sertare
C0, C1, C2
si incercam sa plasam in ele numerele
1,2,...,N
cu proprietatea ca nu sunt TREI numere consecutive in aceasi cutie.
Bine, atunci pot fi maximal doua. De mai multe ori.

Sa luam o alegere posibila.
Avem trei multimi X0, X1, X2 care partitioneaza A = {1,2,...,N}.
Notam aceasta solutie cu X = (X0, X1, X2) , este un triplet.
Notam cu p0, p1, p2 numarul de perechi din X0, X1, X2.
(p0, p1, p2 sunt strict vorbind functii de X. Dar nu vreau sa intru asa in formalizare, o sa pun un X ca argument cand vreau sa vorbesc de functii.)

Desigur ca 2(p0+p1+p2) nu poate depasi N.
Sa zicem ca incercam sa numaram X-urile (asezarile in sertare) pentru care
p0(X), p1(X), p2(X)
iau o valoare fixa,
p0, p1, p2 respectiv.
Notam acest numar cu Asezari( p0, p1, p2 ) .

Daca reusim sa punem mana pe o formula pentruAsezari( p0, p1, p2 ),
putem scrie solutia macar in forma
de "suma dupa toate (p0,p1,p2)-urile posibile din
Asezari( p0, p1, p2 ) .

In combinatorica avem des astfel de solutii.
Indicele sumei nu este tocmai usor de inteles.
Daca nu dam de o formula pentru Asezari( p0, p1, p2 ) care sa se "imbuce" cu aceasta structura de indici, nu putem merge mai departe. Avem insa cat de cat o formula pe care o putem implementa mult mai repede pe calculator, am rezolvat ceva...

Sa incercam asadar sa punem mana pe
Asezari( p0, p1, p2 ) .

Putem sa ne gandim atunci asa.
Incercam sa fixam mai intai locul perechilor (de numere consecutive). Fiecare pereche este bine determinata de primul element din aceasta pereche. Ajunge sa-l alegem pe acesta. In cate moduri putem atunci alege aceste locuri prime de perechi si pentru fiecare alegere cum putem "umple" sertarele (si in cate moduri).

Nu pot sa mai povestesc in aceasta generalitate, trebuie sa iau un caz particular. Sa zicem ca luam N = 20 si (p0, p1, p2) = (3,2,1) .

Cele 3+2+1 perechi de ales vor consuma din 20 exact 2(3+2+1) pozitii.
Mai raman 8 pozitii de umplut nepereche.

In cate moduri putem alege cele 3 pozitii pentru inceput de pereche din C0?
Inceputurile i01,i02,i03 sunt in orice caz din multimea
1,2,...,19
si daca luam prima pozitie i0, locul urmator este ocupat de sfarsitul perechii si apoi i02 nu are voie sa sada in i0+2.
Deci fiecare pozitie rapeste locul ei de plasare si inca doua locuri.
Asa ceva se poate numara repede, problema intervine cand mai incercam sa numaram si inceputurile de perechi pentru C1.
Ei bine, depinde foarte mult de locurile pe care le lasam daca mai incap cele doua perechi in ... Deci numararea aceasta nu este homogena la primul pas. Mai bine renuntam.

Probabil ca putem face rost de o strategie de numarare pentru Asezari( p0, p1, p2 ), dar avem eforturi.
Sa zicem ca am realizat asa ceva.
Atunci trebuie sa mai calculam SUMA din Asezari( p0,p1,p2 )
Psihologic trebuie sa dam de aceasi formula ca cea din recursiunea de mai sus. Pana la urma tot avem nevoie de gasit o recursiune.

Chiar daca reusim sa rezolvam problema pana aici, idea de rezolvare nu se preteaza la generalizare. Nu putem rezolva de exemplu

In cate moduri putem aseza
bilele 1,2,3, ..., 100
in patru cutii colorate diferit (ordinea conteaza)
astfel incat nici o cutie nu contine patru bile consecutive?


Acesta este argumentul principal pentru care nu incerc sa aplic un fel de principiu de includere si excludere (in speranta ca la sfarsit sa pot vedea o relatie de recursiune).

Deoarece suntem "in cautare", cum am mai spus, nu exista nimic gresit, de obicei gasim in ulitimul loc in care cautam! E doar vorba despre modul de cautare si timpul pe care il avem la dispozitie (un lucru esential in viata!). Apoi incercam sa vedem daca experienta dobandita ne ajuta pe viitor.
(Motivul principal pentru care cei "buni in liceu" au probleme in facultate este cresterea exponentiala a volumului de cunostinte si necesitatea organizarii lor, ele nu mai vin digerate nici macar cum veneau la scoala. A nu se subestima incercarea de adunat doar experiente ce se pot ancora si in viitor!)

[Citat] Destul de repede ajungem la relatia de recurenta a(N+2) = 2a(N+1) + 2a(N) , N>2 . Exista desigur si o formula explicita pentru a(N). Trec la formatul in care pot scrie normal formulele. Valorile sunt asadar pentru primele cateva cazuri: sage: F.<u> = QuadraticField(3) sage: F Number Field in u with defining polynomial x^2 - 3 sage: u u sage: u^2 3 sage: for k in [3..10]: ....: print "a(%d) = %d" % ( k, ( (1+u)^(k-2) * (9+5*u) + (1-u)^(k-2) * (9-5*u) ) / 12 ) ....: a(3) = 4 a(4) = 11 a(5) = 30 a(6) = 82 a(7) = 224 a(8) = 612 a(9) = 1672 a(10) = 4568

Imi puteti spune mai multe despre "forma normala Jacobi pentru matricea de recurenta" ? ( se aplica pentru toate relatiile de recurenta de oridnul 2, ajuntand la gasirea formulei?)

Am inteles. Nu am avut destul timp sa continui ideea pentru alte numere de perechi in aceeasi submutime (fara sa iau in considerare ca daca am ales o pereche, atunci imi dispare posibilitatea de a le mai avea si pe celelalte doua impreuna). Am inteles solutia dumneavoastra si aspectul care ii confera "generalitate". Multumesc.

[Citat] ... mai multe despre "forma normala Jacobi pentru matricea de recurenta" ? ( se aplica pentru toate relatiile de recurenta de oridnul 2, ajuntand la gasirea formulei?)

Da! (Raspuns "Divertis" invariabil la nenumarate intrebari cum ar fi: "Care este culoarea steagului purtat de catre pandurii lui Tudor?")

Idea este foarte usor de transmis.
Mai mult, cei ce inteleg din liceu cum merge mecanismul au la facultate un joc mult mai usor. (Este greu de evitat diagonalizarea matricilor si jocurile cu valori proprii la majoritatea facultatilor unde numerele joaca vreun rol.)

Iata cat de repede merg lucrurile.
Daca avem un sir definit de o recursiune liniara cu UN PAS,
x(n+1) = a x(n), orice n natural,
x(0) dat,
atunci este clar ca dam de formula x(n) = a^n x(0) .

Ce facem daca avem un sir definit de o formula de recurenta de ordin mai mare, cum ar fi (iau un caz special ca sa tiparesc mai usor)

x(n+3) = 6 x(n+2) - 11 x(n+1) + 6 x(n)
x(0), x(1), x(2) date / fixate

?

Idea este simplu de descris. Asociem sirul y(n) cu mai multe componente, dar cu recursiunea de UN PAS in care y(n) este matricea 3x1 (vector coloana)

[ x(n+2) ]
[ x(n+1) ]
[ x(n+0) ]

Atunci este clar ca imediat putem izola o matrice A de dimensiune 3x3 cu proprietatea ca

y(n+1) = A y(n) .

Instantaneu scriem aceasi formula pentru termenul general.
Intervine problema calcularii matricii A^n .

Idea diagonalizarii si a folosirii ei in astfel de cazuri este naturala.
(Diagonalizarea este foarte utila in calculul functional aplicat pe A, exista retete de facut asa ceva. Daca se poate face asa ceva. Mai mult mai incolo.)

Daca A este o matrice diagonala
D = diag( a,b,c,...,z )
atunci ridicarea la putere este imediata, ridicam la putere elementele de pe diagonala.

Daca nu, incercam sa "schimbam baza", reformuland pentru clasa a XI-a, incercam sa scriem

A = S D T
unde T este inversa lui S, ST = TS = I.
(Nu pot scrie in ASCII acea putere la minus unu.)

Atunci
AA = SDT SDT = S D TS D T = S D I D T = S DD T ,
AAA = SDT SDT SDT = S D TS D TS D T = S D I D I D T = S DDD T ,
:
:

si este clar ca am castigat!
Cu alte cuvinte, intelegerea diagonalizarii matricilor rezolva in mod *natural* recurentele liniare de siruri. (In momentul in care stim "cum arata solutia", stim sa demonstram totul si prin inductie. Intervin atunci in culegeri propozitii de forma "asociem ecuatia caracteristica a recursiunii liniare date", propozitii care pe mine m-au iritat mult in liceu. Secretul se putea povesti intr-o nota de subsol. Secretul nu este inductie, nici "ghicirea formei solutiei" cu toate "cazurile particulare", secretul este diagonalizarea matricilor.)

Inainte de a merge mai departe am o mare rugaminte.

Sa incercam sa diagonalizam mattricile

[ 2 2 ]
[ 1 0 ]

si cea ce corespunde / se extrage din recursiunea particulara pe care am luat-o eu mai sus.

Informatia utila este urmatoarea:
Elementele de pe diagonala matricii sunt (daca putem diagonaliza!) exact radacinile polinomului

P(x;A) = det( xI - A ) ,
x variabila din corpul unde traiesc intrarile lui A

numit "polinom caracteristic al lui A" .
(Pentru a nu introduce prea multe minusuri la trecerea de la A la P(x;A), eu am mereu probleme cu transcrierea, unii oameni se leaga de det( A - xI ). Semnul se schimba uneori, radacinile raman.)

Care este deci rescrierea
A = S D T , unde S,T sunt inverse una alteia, D matrice diagonala,
pentru cele doua matrici particulare (2x2, respectiv 3x3)?

Acest exercitiu comprima algebra liniara de faculatate, este util pentru matematicieni, mai util pentru fizicieni. Ca arma de putata in olimpiade este de mare folos, se vede problema cu structura cu tot de la inceput, daca are de-a face cu asa ceva. (Nu dau inca link-uri.)

Am inteles cum am gasit pe D, dar pe S cum il obtinem?

[Citat] Am inteles cum am gasit pe D, dar pe S cum il obtinem?

Care este atunci explicit acest D pentru matricea
2 2
1 0
mai intai? Propun sa folosim litera u pentru radical(3).
Apoi mai vedem

Care este A-ul pentru recurenta de ordin 3 de mai sus?
Care este matricea diagonala D din acest caz?
Apoi mai vedem.

D-ul l-ati scris dvs mai sus(mult mai sus, de fapt pe prima pagina) si este (1+u 0 // 0 1-u) ,iar celelalte 2 intrebari sunt chiar foarte bune :D !

Bine, cer scuze, ghicitoarea a fost totusi prea aluziva, o sa incerc sa pun problema intr-un exemplu didactic din care sa se inteleaga cum merge de fapt teoria, aplicarea ei mai exact. (Nu se intelege / nu se teoria, ci doar aplicarea ei, o instanta a ei care inlesneste drumul.)

Trec la latex.

Care este deci situatia cu A-ul de mai sus
0 1 0
0 0 1
6 -11 6

?
Care este descompunerea A = S D T cu S,T matrici inverse una alteia, D matrice diagonala?

Nota: Aceasta "tema" este foarte importanta, o recomand pentru toti cei amenintati de o facultate (politehnica, matematica, fizica, economie).

Nu inteleg ce e vectorul e_i ! (nu stiu despre ce e vorba, adica nu cred ca poate fi o matrice, astfel am avea un produs de matrici egal cu 0 (ceea ce nu cred ca e posibil) si un vector la geometrie nu are ce cauta aici :D ) E cumva legat de spatiile vectoriale?