Problema tip OIM (proprie)

[laurentiu]

Fie [tex]M_n(Z_p) [/tex] multimea matricilor n x n cu elemente in [tex]\mathbb{Z}_p[/tex].Pt o matrice diferita de [tex]O_n[/tex] numim operatie adunarea cu [tex]1[/tex]la un elemente nenul [tex]a_{ij}[/tex].In cazul in care in urma unei operatii elementul respectiv devine [tex]0[/tex],atunci primelor numere vecine nenule de pe linie si de pe coloana li se aduna 1 ,iar operatia poate continua .O operatie se opreste in cazul in care niciun numar nu se mai anuleaza .
a)Pt. [tex]A\in M_4(Z_5)[/tex],definita prin [tex]A=\begin{pmatrix} 3 & 0 & 2 & 0 \\ 3 & 0 & 3 & 3 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 4 & 3 \end{pmatrix}[/tex],sa se arate ca putem face 4 operatii a.i. A sa devina [tex]O_4[/tex].
b)Pt o matrice [tex]B\in M_n(Z_n) [/tex] ,notez cu [tex]m_n(B) [/tex] numarul minim de operatii pana cand matricea devine [tex]O_n[/tex].Luand [tex]B=\begin{pmatrix} 0 & 1 & . & . & . & {n-1} \\ 1 & 2 & . & . & . & 0 \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ . & . & . & . & . & . \\ {n-1} & 0 & . & . & . & {n-2} \end{pmatrix} [/tex]. Sa se calculeze [tex]S_n=\sum_{k=2}^n m_k[/tex].

PS:o promovez aici deoarece daca o pun pe un site de matematica ,nu voi mai putea sa o propun la un concurs ,sau chiar la balcaniada sau OIM ,depinde cat de grea este vazuta rezolvarea de cei ce aleg problemele.

[florin_try]

Am citeva neclaritati referitoare la notatii:
1. deci cind adun 1 la [tex]a_{i,j}\ne 0 [/tex] si daca noul [tex]a_{i,j}[/tex] devine [tex]0[/tex] , atunci doar elementele de tipul:
    [tex] a_{i,j+1},a_{i+1,j},a_{i-1,j},a_{i,j-1} [/tex]
se incrementeaza cu 1.
poti confirma ca am notat bine "vecinii" pentru i,j intre 2 to n-1 ? Sau mai sunt si altii? (bine, operatia se aplica recursiv la fiecare din vecini in parte, asta insa e alta treaba, eu ma refer strict la o singura secventa a recursivitatii care sunt vecinii.)

2. Cum definesti vecinii lui [tex]a_{1,1}[/tex]? Doar [tex]a_{1,2}[/tex] si [tex]a_{2,1}[/tex] ?
Daca nu, poti sa ii scrii explicit vecinii lui  [tex]a_{1,1} [/tex]si [tex]a_{n,n}[/tex]. Sau vecinii elementelor de pe prima linie sau coloana? Vreau sa zic, au cumva vre-o simetrie in sensul ca prima linie e vecina cu ultima? (ce bine ar fi sa fie asa ... )

3. Inteleg ca in [tex]Z_5[/tex] avem [tex]4+1 \equiv 0 [/tex], corect?

Intrebarile puse se refera la notatii, nu cred ca dai nici un hint privind rezolvarea daca clarifici ce am intrebat.

[florin_try]

OK, probabil m-am prins cum e cu notatiile. Puntul a) e banal de simplu.
Pornesc de la: [tex]A0=\left( \begin{array}{cccc}
3&0&2&0 \\
3&0&3&3 \\
0&0&0&0 \\
1&0&4&3 \end{array}\right) [/tex]


Iata pasii:
1) pasul 1 , 2 , si 3 : Aplic operatia O respectiv elementelor: [tex]a_{1,1}, a_{1,2}, a_{2,3}[/tex]. In urma acestor 3 pasi obtin matricea:
[tex]A^{(3)}=\left( \begin{array}{cccc}
4&0&2&0 \\
4&0&4&3 \\
0&0&0&0 \\
1&0&4&3 \end{array}\right) [/tex]

Pe urma in pasul 4 "ii dau foc" ca sa zic asa, si aplic operatia O elementului  [tex]a_{2,3}[/tex]
Folosind ca 5=0 si recusivitatea descrisa de tine , in final se obtine la capatul unui lant recusiv la matricea ZERO ( e simplu de verificat).

La punctul b o sa ma mai gindesc. Ideea ar fi sa ai un lant recusiv cit mai mare. Adica generezi graphul care cu cele mai multe conexii intre elemente.

[florin_try]

punctul b)
In matricea generala data toate elementele "diagonale secundare" au proprietatea:
[tex]a_{N-j+1,j}= n-1[/tex]
unde j=1..N
Elementele imediat de deasupra "diagonalei secundare" au proprietatea:
[tex]a_{N-j+1+1,j}= n-2 [/tex]
cu unde j=1..N-1

In primii N-1 pasi aplici operatia O elementelor imediat deasupra diagonalei secundare
[tex]a_{N-j+1+1,j}= N-2 , j=\bar {1,N-1} [/tex]
iar in orma acestor N-1 operatii aceste elemente devin:
[tex]a_{N-j+1+1,j}= N-1 , j=\bar {1,N-1} [/tex]

In pasul N aplici operatia O oricarui element care este egal cu N-1
(sa zicem [tex]a_{1,n}[/tex])
Daca nu ma insel, recursivitatea operatiei tale (asa cum ai definit-o tu ca se aplica recursiv)  asupra matricii va anula toate elementele.
Daca insa ma insel.... sunt cam lenes ca puteam scrie un mic cod sa verific....

Deci eu cred ca numarul de pasi este N unde N e numarul de linii (egal cu cel de coloane a matricii). Daca e asa, apoi suma data de tine e trivial de calculat.
[tex]\sum_{i=2}^M i = \frac{M(M+1)}{2}+1[/tex]

Daca e asa, apoi pare cam simplu, ca eu nu am mai facut cam demult mate.

[laurentiu]

E corect ce ai spus ,insa mai ramane demonstrarea minimalitatii .