4
$\begingroup$

Consider the following puzzles:

Problem 1: Alice is given two data by Zora: a binary string $w$ of length $2^r$, and a position $p$ in the string (which we can view as an integer $0\leq p<2^r$). Alice's goal is to communicate $p$ to Bob (her accomplice). To this effect, she can (and must) modify a single bit in the string, producing a different string $w'$. (The bit modified by Alice is at a position $q$ of Alice's choosing.) Bob only gets to see $w'$ (but not $w$ nor $q$, nor, of course, $p$) and his goal is to correctly deduce $p$. What protocol (agreed in advance) can Alice and Bob use to perform this trick?

and

Problem 2: Alice is given $5$ cards (out of a usual $52$-card deck) by Zora. Alice's goal is to communicate one of these cards to Bob (her accomplice). To this effect, she removes one of the $5$ cards and places the remaining $4$ in a certain order on the table. Bob only gets to see the quadruple of remaining cards (in the order chosen by Alice) and his goal is to correctly deduce the fifth (removed). What protocol (agreed in advance) can Alice and Bob use to perform this trick?

I know a solution to both, but this is not my question; here is a sketch:

  • Problem 1: consider the binary Hamming code of length $2^r-1$ (bits numbered $1$ through $2^r-1$), augmented by a dummy bit ($0$): namely, it is the set $\mathcal{C}$ of binary strings of length $2^r$ such that the XOR (=nim-sum) of all $i$ such that bit number $i$ is $1$, equals $0$. Alice will communicate $p$ to Bob as an error syndrome. Namely, she mentally flips bit $p$ in $w$, giving a modified word $w^*$, then finds the unique codeword (element of $\mathcal{C}$) $w''$ which differs from $w^*$ in exactly one position $q$, then she flips bit $q$ in $w$ to produce $w'$. To recover $p$, Bob finds the unique codeword $w''$ which differs from $w'$ in exactly one position, and the position in question is $p$.

  • Problem 2: among the $5$ given cards, two have the same suit and their numbers are at distance at most $6$ in $\mathbb{Z}/13\mathbb{Z}$: hide the larger one, place the smaller first, and use the order of the remaining three to code a number between $1$ and $6$.

These make for nice little parlour tricks (the first can be realized with coins or reversi pieces on a chessboard, perhaps a $4×4$ board to make it more manageable), but I'm disappointed by their very ad hoc character. I'd like a more general result or theory "explaining" how to solve these problems. So:

Question: is there a general theory, or a general result, behind these puzzles? If so, how can we formalize them and solve them in greater generality?

PS: I just realized that problem 2 is also stated here.

$\endgroup$
  • 1
    $\begingroup$ Maybe you'll find something in Diaconis & Graham, Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks, Princeton University Press 2012. $\endgroup$ – Gerry Myerson Dec 3 '18 at 21:42
  • $\begingroup$ These kind of puzzles seem to be related to subliminal/covert channels, which are always present in any kind of communication/storage modification context. The prerequisite to them working is that two parties have agreed ahead of time, what the structure to be used is. What do you mean by "explaining how to solve"? Someone gives you the puzzle and you figure out what mathematical property is being used? $\endgroup$ – kodlu Dec 4 '18 at 23:46
  • $\begingroup$ @kodlu What I'd like is, for example, a general theorem that encompasses both of these puzzles and that predicts how many bits of information Alice can pass to Bob given the set of rules that she must apply. $\endgroup$ – Gro-Tsen Dec 5 '18 at 10:06
  • $\begingroup$ Re the comment directly above, why isn't the answer just the log (base 2) of the number of options available to Alice? $\endgroup$ – Steven Landsburg yesterday

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.