A magician and his assistant perform in front of an audience of many people. On the stage there is an $8$×$8$ board, the magician blindfolds himself, and then the assistant goes inviting people from the public to write down the numbers $1, 2, 3, 4, . . . , 64$ in the boxes they want (one number per box) until completing the $64$ numbers. After the assistant covers two adyacent boxes, at her choice. Finally, the magician removes his blindfold and has to $“guess”$ what number is in each square that the assistant. Explain how they put together this trick. $Clarification:$ Two squares are adjacent if they have a common side
Problem
Source: 2009 Peru Iberoamerican TST Problem 2
Tags: combinatorics, Magician, Tables
10.05.2023 14:06
Claim: there exists a path that starts in one square, goes through all the squares on the chessboard exactly once, and ends back at the original square (so the path is cyclic), and on each step the path goes from one square to adjacent square. Proof: there are many such paths. Start from top left, go to top right, go to bottom right, then left by 1, go up all the way to second row, go left by 1, and so on. Now, to make the problem simpler, pretend the numbers are 0 to 63 (replace 64 by 0). Number all the squares with 0 to 63 according to the path above (0 goes to 1 goes to 2 etc). Magician and assistant should agree on which square is the square zero, and what the path looks like, so from there the number of each square is fixed. When the audience writes the numbers on the board, let $a_k$ be the number written on square $k$. The assistant calculates $S =0 . a_0 + 1 . a_1 + 2.a_2 + \dots + 63.a_{63} \mod 64$ and then covers square $S$ and $S+1$ (because they must be adjacent, by the construction of the path). When the magician removes the blindfold, he sees which squares are covered, so he knows $S$. Because he sees 62 numbers on the board, he can infer the 2 missing numbers $a_S$ and $a_{S+1}$. So he can also calculate $S.a_S + (S+1)a_{S+1} \mod 64$ He can then calculate: $a_{S+1} = S.a_S + (S+1)a_{S+1} - S(a_S + a_{S+1}) \mod 64$ and quickly deduce $a_{S+1}$. From there he can deduce $a_S$.