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: Gurmeet Singh Manku's Blog where he said that he saw it in an old Russian problem book.

Solution:
Highlight the part between the * symbols for the answer.
* There are 36 3×3 blocks and 25 4×4 blocks. Given a sequence of blocks, the same effect is achieved no matter in what order the blocks are chosen. If the same block occurs two times in a sequence, their effect is nullified. Thus, a sequence of blocks is equivalent in effect to some subset of the 36 + 25 = 61 blocks. Starting with all zeros, at most 2^61 distinct configurations out of 2^64 possible configurations of the matrix can be reached. This means that we may not be able to remove all the ones from the original matrix. *

Fundoo question!!

Comments

  1. an easier solution might be to consider the counter-example of an 8X8 matrix with one corner being 1 and the rest being zeros. This corner can be "affected" by only two 3X3 or 4X4 blocks and thus, it can never be changed to a 0 without changing something else too.
    QED.

    ReplyDelete
  2. @omkar

    We can have a series of 3X3 or 4X4 matrix. In your example, its obvious that one cannot do it in 1 operation. How can you prove that its not possible to do this by a series of operations?

    ReplyDelete

Post a Comment