Flipping Bits in a Matrix
12 Sep 2008
Puzzle

An 8×8 matrix contains zeros and ones. You may repeatedly choose any 3×3 or 4×4 block and flip all bits in the block (that is, convert zeros to ones, and ones to zeros). Can you remove all the ones in the matrix?

Source

From an old Russian problem book that I had in 1991: The USSR Olympiad Problem Book: Selected Problems and Theorems of Elementary Mathematics (452 pages, 3rd revised ed, 1993) by D O Shklarsky, N N Chentzov and I M Yaglom.

Solution

Given a multi-set of blocks and a starting configuration of the 8×8 matrix, the final configuration of the matrix is the same, independent of the sequence in which the blocks in that multi-set are applied. In fact, we can reduce the multi-set to a set (with no repeated blocks) by recognizing that application of the same block twice has no effect.

There are 36 3×3 blocks and 25 4×4 blocks. The total number of sets of blocks is 236 times 225 = 261. So starting with a matrix full of zeros, at most 261 distinct configurations out of 264 possible configurations of the matrix can be obtained. In other words, we may not be able to remove all the ones from the original matrix.