The Magic Trick



The Trick & Background

We set up the board such that each row contains an even number of green and brown tiles. When a single tile is flipped over the particular row and column of this tile now have an odd number of green tiles. The magician only needs to look for this column and row and will find the treasure at their intersection.

In the context of computer science we can think of each tile as a bit: bits are the smallest amount of information and correspond to a yes/no decision. We usually write 0 and 1 for a bit and represent larger pieces of information as a series of bits. Each tile of the game represents a bit of information; instead of numbers we use the colours green and brown.

The actual magical trick comes from a technique called error correction. If we have to send data over an unreliable connection it is possible that a bit is transferred erroneously -- it flips from zero to one or vice versa. The same happens when we bury the treasure. The additional tiles we have added allow us pinpoint which bit flipped. In computer science, this additional information is called a parity bit.

This particular error correction scheme can always correct a single mistake. If two bits changed we can still detect that there is a mistake but we cannot find out where. In terms of the board game, it could happen that we flip the second tile in the same row as the first. Now the number of green tiles in that row is again even but we can still see two columns that have an odd number of green tiles. The situation when a third error is introduced. But when four errors happen on tiles that are arranged in a rectangle, the all counts add up to even numbers again.

Computer Scientific Lessons


about me · research · publications · teaching · outreach · software · contact · home