Gurmeet.Net
Gurmeet.Net
Puzzles
Puzzles

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?

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.

Previous Puzzle: Polya's Urn Process

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.