Fie

o matrice cu elemente consecutive:


A =
(1 2 3 4 ...n)
(n+1 n+2 ....)
(............)
(...n^2-1 n^2)

Sa se demonstreze ca pentru orice m < n, suma a exact m elemente din matrice, selectate de pe fiecare linie si de pe fiecare coloana este aceeasi.

Am reusit sa demonstrez pentru cazuri in care m este un numar dat (n = 3 sau 4 ), insa pentru n general nu mi-a iesit.

[Citat] Fie o matrice cu elemente consecutive: A = (1 2 3 4 ...n) (n+1 n+2 ....) (............) (...n^2-1 n^2) Sa se demonstreze ca pentru orice m < n, suma a exact m elemente din matrice, selectate de pe fiecare linie si de pe fiecare coloana este aceeasi. Am reusit sa demonstrez pentru cazuri in care m este un numar dat (n = 3 sau 4 ), insa pentru n general nu mi-a iesit.

Nu în?eleg enun?ul. Cum sunt selectate cele m elemente? Dar daca m=1?
Pute?i s? ne ar?ta?i cazul n=3, de exemplu?

Eu cunosc urm?toarea problem? (e în Mathematical Olympiad Treasures):

Elementele matricei sunt aranjate exact ca in tabloul desenat de dumneavoastra.

Pentru n = 3 si m = 1, pot selecta elementele de pe diagonala principala sau secundara(singura cale).

Pentru n = 4 si m = 3, selectez elementele de pe o diagonala si cele de langa:

Unde a [ i ] [j] e 1 daca e selectat.Astfel, sunt selectate exact 3 elemente de pe FIECARE LINIE SI FIECARE COLOANA. Practic, eu vreau sa demonstrez ca oricum as selecta cele m elemente, suma e aceeasi, adica mai pot selecta si elementele de pe diagonala secundara si celelalte aranjate la fel:

Si suma acestor elemente selectate e egala cu suma elementelor selectate in primul caz.

Problema asta seamana cu una de clasica de informatica. In acest caz, eu as considera alta matrice de acelasi ordin. Sa-i zicem L, in care L contine toate sumele partiale ale elementelor de pe FIECARE LINIE a matricei initiale. In felul acesta, ar fi mai usor de lucrat. Am realizat un program in c++, iar suma celor m elemente de pe fiecare linie si fiecare coloana este aceeasi, indiferent de selectie, insa redactarea "matematica" nu mi-a iesit inca...

[Citat] Pentru n = 3 si m = 1, pot selecta elementele de pe diagonala principala sau secundara(singura cale).

Nu e singura cale.

Dac? în?eleg bine, enun?ul, de fapt, este a?a: fiind dat? acea matrice, s? se arate c? oricum am alege nm elemente, astfel încât de pe fiecare linie ?i de pe fiecare coloan? s? fie alese exact m, suma acestora este aceea?i.

Dac? e a?a, e doar o extindere a problemei postat? de mine (care corespunde cazului m=1).

Imi puteti spune va rog cum as mai putea selecta elementele?

[Citat] Dac? în?eleg bine, enun?ul, de fapt, este a?a: fiind dat? acea matrice, s? se arate c? oricum am alege nm elemente, astfel încât de pe fiecare linie ?i de pe fiecare coloan? s? fie alese exact m, suma acestora este aceea?i. Dac? e a?a, e doar o extindere a problemei postat? de mine (care corespunde cazului m=1).

Da, asta cere problema, insa nu stiu cum sa demonnstrez exact.

EDIT: De fapt, problema postata de dumneavoastra satisface cazul m = 1.
Nu s-ar putea face vreo inductie dupa m?

[Citat] Imi puteti spune va rog cum as mai putea selecta elementele?

Da: a11,a23,a32, sau a12,a21,a33, sau a13,a21,a32, sau a12,a23,a31.

[Citat] De fapt, problema postata de dumneavoastra satisface cazul m = 1.

Nu exact asta am spus?

Ba da. Insa, nu ar fi corecta o inductie dupa m? De exemplu, sa consideram ca pentru m, cerinta e satisfacuta, iar noi trebuie sa demonstram ca p(m) implica p(m+1), adica pentru m+1, cerinta e adevarata.

M-am gandit in felul urmator: in matrice, selectez m elemente de pe fiecare linie si fiecare coloana. Stiu ca pentru m, cerinta e satisfacuta si pentru m+1 elemente, trebuie sa mai consider un set de n elemente in plus fata de acela. Si pentru m = 1 e la fel satisfacuta relatia, mai precis pentru n elemente selectate in afara de celelalte mn.