Problem
COM-B2-M05-P020 Switching Rows and Columns
On an \(m\times n\) board, all cells are white. In one move, choose a row or a column and change the colours of all cells in it. Prove that every reachable colouring has the property that the corners of any rectangle contain an even number of black cells. Also prove the converse: if a colouring has this property, then it can be obtained by such moves.
Write the colour of a cell as the modulo \(2\) sum of a row variable and a column variable.
Represent a cell colour by \(0\) for white and \(1\) for black. If rows are switched according to variables \(r_i\in\{0,1\}\) and columns according to variables \(c_j\in\{0,1\}\), then the colour of cell \((i,j)\) is \(r_i+c_j\pmod2\).
For the rectangle corners \((i,j),(i,l),(k,j),(k,l)\), the sum of colours is
\[(r_i+c_j)+(r_i+c_l)+(r_k+c_j)+(r_k+c_l)\equiv0\pmod2.\]
Thus the number of black corners is always even.
Now prove the converse. Let a colouring \(a_{ij}\) have this property. Set \(r_i=a_{i1}\) for every row and \(c_j=a_{1j}+a_{11}\) for every column. Applying the rectangle condition to rows \(1,i\) and columns \(1,j\), we get
\[a_{ij}+a_{i1}+a_{1j}+a_{11}\equiv0\pmod2.\]
Hence \(a_{ij}=r_i+c_j\pmod2\). Therefore it is enough to switch all rows with \(r_i=1\) and all columns with \(c_j=1\). The colouring is reachable.
This is a full reachability criterion, so the problem is level 5.