Here's a problem. The devil has captured two people and is playing a game with them for their freedom. Person A will be presented with a chessboard with a penny in each square (64 total), with each penny either heads up or tails up randomly. The devil will choose a particular square and point it out to Person A. Person A then chooses a single square, and flips the penny in that square. Afterward, Person A is sent away and Person B is brought forward. Based on the new state of the board, Person B must point out the same square that the devil did in order to win. The two people can devise a strategy beforehand, but cannot communicate once the game starts. How can they win?
Here's another problem. Alice wants to transmit a sequence of bits to Bob through a communication channel. But Eve has the ability to discreetly flip at most a single bit in the message that Alice sends to Bob. Is there a way for Alice to add some redundancy in her messages so that Bob can figure out when a bit has been flipped and also correct it?
These two problems are connected, and we will see how.
