Maths WorkshopMaths problems with full solutions
Exercise 1238Combinatorics › Counting principlesOlympiadAdded 4 Nov 2026

Flipping rows and columns of a board

#invariant#parity#colouring#moves

Statement

The squares of an n×nn\times n board (n≥2n\ge2) are all white. A move chooses one row or one column and changes the colour of every square in it. Prove that it is impossible to obtain a board with exactly one black square.

Hint

Look at a 2×22\times2 block formed by two rows and two columns, and count its black squares modulo 22.

Show solutionHide solution

Solution

Idea. Find a quantity that no move can change.

Invariant. Fix two rows r≠r′r\ne r' and two columns c≠c′c\ne c', and consider the four squares (r,c),(r,c′),(r′,c),(r′,c′)(r,c),(r,c'),(r',c),(r',c'). Look at the parity of the number of black squares among these four.
- A move on row rr (or r′r') changes exactly two of them.
- A move on column cc (or c′c') likewise changes exactly two.
- A move on any other row or column changes none of them.

Changing two squares changes their black count by −2-2, 00 or +2+2: the parity of the black count is invariant.

Conclusion. At the start this number is 00, so it stays even forever. Now suppose a board with a single black square (a,b)(a,b) could be reached. Choose any other row r′≠ar'\ne a and column c′≠bc'\ne b and the block of the rows a,r′a,r' and columns b,c′b,c': it contains exactly one black square, an odd number. Contradiction.

Remark. The reachable boards are exactly those in which every 2×22\times2 block has an even number of black squares.

Lesson. Invariant: restrict attention to a small sub-configuration on which each move acts in a controlled way.