binaire matrix

Opgave - IrMO 1994 dag 2 vraag 1

Een $n\times n$ matrix heeft alle elementen gelijk aan 0 of 1. Vind het aantal matrices met een even aantal enen in iedere rij en kolom.

Oplossing

Het aantal matrices is $2^{\left((n-1)^2\right)}$. We kunnen namelijk linkerboven $(n-1)\times(n-1)$-deelmatrix willekeurig kiezen, en daarna liggen alle andere vakjes uniek vast: elke rij of kolom moet een even aantal enen hebben, wat alles buiten het rechterondervakje vastlegt, en dit laatste vakje moet nu ook uniek vastliggen, want de som van alle getallen in de matrix moet uiteraard ook even zijn.

Zie ook onze breinbreker van september-oktober 2009.