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?

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.

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 2³⁶ times 2²⁵ = 2⁶¹. So starting with a matrix full of zeros, at most 2⁶¹ distinct configurations out of 2⁶⁴ 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.