Flipping rows and columns of a board
Statement
The squares of an board () 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 block formed by two rows and two columns, and count its black squares modulo .
Show solutionHide solution
Solution
Idea. Find a quantity that no move can change.
Invariant. Fix two rows and two columns , and consider the four squares . Look at the parity of the number of black squares among these four.
- A move on row (or ) changes exactly two of them.
- A move on column (or ) likewise changes exactly two.
- A move on any other row or column changes none of them.
Changing two squares changes their black count by , or : the parity of the black count is invariant.
Conclusion. At the start this number is , so it stays even forever. Now suppose a board with a single black square could be reached. Choose any other row and column and the block of the rows and columns : it contains exactly one black square, an odd number. Contradiction.
Remark. The reachable boards are exactly those in which every 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.