## Flipping Bits in a Matrix

### 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?

### 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 2^{36} times 2^{25} = 2^{61}. So starting with a matrix full of zeros, at most 2^{61} distinct configurations out of 2^{64} 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.

There are two urns with one ball each. Each of subsequent n-2 balls is placed into one of these urns, with probability proportional to the number of balls already in that urn. What is the expected number of balls in the urn with fewer balls?

A big rectangle is composed of smaller non-overlapping rectangles, each having integer width or integer height or both. Prove that the big rectangle enjoys the same property.

###### 12 Sep 2008

© Copyright 2008—2017, Gurmeet Manku.