Soluţia problemei Matrice echilibrata

Observăm că suma elementelor matricei este suma = N * X = M * Y, altfel nu exista soluţie. Presupunem mai întai că X, Y sunt coprime. Fie p = cmmdc( N, M). Cum X şi Y sunt coprime rezultă că N * X = M * Y = cmmmc( N, M) = N * M / p. Deci X = M / $p, Y = N / p. Împărţim matricea în bucăţi de N / p pe M / p. Acum, fiecare rând trece prin M / ( M / p ) = p submatrici. Fiecare coloană trece prin N / ( N / p )) = p submatrici. Aşadar, ne putem imagina că avem o matrice de p × p elemente, fiecare element fiind defapt o submatrice de dimensiuni N / p × M / p = X × Y. Observăm că este suficient să completam toate elemenetele submatricilor de pe diagonala principală cu 1, şi aşa vom avea pe fiecare rând X elemente de 1 si pe fiecare coloană Y elemente de 1.

Presupunem acum ca gcd( X, Y) = q. Atunci N * X / q = M * Y / q = cmmmc( N , M) = N * M / p. Deci X= M * q / p şi Y = N * q / p. Cum X < M rezultă că q < p. La fel ca înainte deci putem împărţi în bucăţi de N / p pe M / p, şi luăm q diagonale "principale" şi le umplem cu 1-uri. Practic, pe fiecare linie completăm elementele primelor q submatrici cu 1. Atunci fiecare linie o să aibă M * q / p = X elemente, şi analog la coloane.