Personal tools
You are here: Home High School Presentation What is Computer Science Activities Error Correction Secret

Error Correction Secret

This trick uses what is called a parity check. We explain it here in the context of the 8x8 grid.

A simpler but possibly less impressive approach for this trick (as it appears in a CS Unplugged activity) would be as follows. After letting someone choose an arbitrary 7x7 pattern of blacks and whites, we would add an 8th row and column. The colors added in the 8th row and column would be chosen to ensure that the first 7 rows and the first 7 columns each have an even number of white tiles. Then, when the volunteer flips one tile, we would see which of the first 7 rows contains an odd number of white tiles (if none, the flip was in the 8th row). Similarly, we would see which of the first 7 columns contains an odd number of white tiles (if none, the flip was in the 8th column). The intersection of the relevant row and column indicates which tile was flipped.

The way we actually ran the trick was to allow an arbitrary 8x8 pattern and then to bring the array into order similar to the approach discussed above. The key observation here is that we could choose to arrange either to have an even number of white tiles (even parity) or an odd number of white tiles (odd parity) in each of the first 7 rows; similarly, we could choose to arrange either even parity or odd parity for each of the first 7 columns. With some thought, you should be able to convince yourself that at most 3 tiles need to be flipped in an 8x8 grid to make the first 7 rows have the same parity and also make the first 7 columns have the same parity. The organize button quickly identifies a small set of tiles to flip to achieve this. Then, when the volunteer flips one tile, we just see which of the first 7 rows has a different parity than the others (if none, we know the flip was in the 8th row). Similarly, we look for a column among the first 7 that has different parity than the others to determine which column contains the flip.

If you would like to look at references that include this trick and other versions (including a version that can handle an arbitrarily large grid with just one organizing flip), as well as illuminations of how the tricks work, start at http://rig.cs.luc.edu/~rig/fie.

Document Actions