Friday, March 11, 2022

Impossible chessboard puzzle

Easy case: You start with an 8*8 chessboard and there is 1 coin on each square. In the initial configuration, all coins are placed tails up. You need to communicate a message to me by flipping exactly 1 coin. How many bits can you communicate? Answer is log_2(64)=6 bits. First number thr coins as 0,1,2,...63. Then you simply convert the 6 bits you want to communicate to decimal and flip the coin whose index is the decimal number. Harder question: Dirty paper coding. Now the initial configuration of the coins is completely arbitrary, each coin can be heads or tails. You are still allowed to flip exactly 1 coin and you need to communicate 6 bits. How can you do this? Don't type "impossible chessboard puzzle" on google or youtube, that is considered cheating.