Această problemă este destul de des întâlnită la concursurile de programare şi pune unele dificultăţi deoarece toate variabilele depind între ele, problema neputând fi împărţită în subprobleme. Pentru a rezolva problema vom asocia sistemului o matrice în care pentru fiecare ecuaţie vom pune pe linia ei şi coloana corespunzătoare variabilelor care apar în ecuaţie valoarea $1$, iar pe ultima coloană vom pune rezultatul ecuaţiei. Matricea obţinută vom încerca să o reducem. Pentru a o reduce vom folosi două operaţii:
<tex>L_{i} \longleftrightarrow L_{j}</tex> : interschimbarea a două linii
<tex>L_{j} \longleftarrow L_{j} \oplus L_{i}</tex> unde <tex>L_{i}</tex> este o linie a matricei.

Având matricea redusă, numărul de soluţii este dat de numărul de coloane, fie el $x$, pe care nu am putut găsi un $1$ cu care să reducem liniile de mai jos. Astfel celelalte variabile vor fi determinate în funcţie de variabila corespunzătoare acestei coloane, sistemul avand soluţie indiferent de valoarea variabilei. În final numărul de soluţii va fi <tex>2^x</tex>

Având matricea redusă, numărul de soluţii este dat de numărul de coloane, fie el $x$, pe care nu am putut găsi un $1$ cu care să reducem liniile de mai jos. Astfel celelalte variabile vor fi determinate în funcţie de variabila corespunzătoare acestei coloane, sistemul avand soluţie indiferent de valoarea variabilei. În final numărul de soluţii va fi <tex>2^x</tex>.  Sistemul nu are soluţie atunci când avem o linie de forma <tex>\begin{pmatrix} 0 & 0 & 0 & 0 & 0 & 1\end{pmatrix}</tex>

h2(#go2). 'Go2':problema/go2 (Algoritmiada 2012 runda 4)

h3. Soluţie

În mod evident o primă soluţie ar fi să considerăm fiecare celulă o necunoscută şi pentru fiecare informaţie să introducem o ecuaţie în sistem. Astfel vom avea $N*N$ necunoscute, ceea ce este prea mult pentru a intra în timp. În continuare vom lucra cu matricea $M[i][j]$ = suma xor a elementelor care se afla în submatricea $(1,1)$ $(i,j)$, astfel pentru o informaţie x1, y1, x2, y2, r vom şti că $M[x2][y2]^M[x1-1][y2]^M[x2][y1-1]^M[x1-1][y1-1]=r$. Vom aplica eliminarea gaussiană pe această matrice.

În mod evident o primă soluţie ar fi să considerăm fiecare celulă o necunoscută şi pentru fiecare informaţie să introducem o ecuaţie în sistem. Astfel vom avea $N*N$ necunoscute, ceea ce este prea mult pentru a intra în timp. În continuare vom lucra cu matricea $M[i][j]$ = suma xor a elementelor care se afla în submatricea $(1,1)$ $(i,j)$, astfel pentru o informaţie x1, y1, x2, y2, r vom şti că $M[x2][y2] ^ M[x1-1][y2] ^ M[x2][y1-1] ^ M[x1-1][y1-1] = r$. Vom aplica eliminarea gaussiană pe această matrice.

'The magic matrix':http://community.topcoder.com/stat?c=problem_statement&pm=12495
https://apps.topcoder.com/wiki/display/tc/TCO+2013+Round+2A#TheMagicMatrix