A concise way to see how the usual “error‐correcting code” strategy works is as follows:
- Pre-game agreement on a “covering code.”
Before play begins, Alice and Bob agree on a fixed set of 9-bit “codewords” (each codeword is just a length-9 sequence of H’s and T’s, or equivalently 0’s and 1’s). They choose this set so that every possible 9-bit sequence lies within Hamming distance 4 of at least one codeword. In coding theory terms, they want a code whose covering radius is 4.
Concretely, this means: for any actual sequence of 9 coin tosses that the casino might produce, there is at least one codeword in their list that differs in at most 4 positions from that actual sequence.
- Bob picks the “closest” codeword and guesses accordingly.
Once the casino fixes the 9-heads/tails sequence (and shows it secretly to Bob), Bob identifies which codeword ccc in their agreed-upon set is within distance 4 of the actual sequence sss. - In every position where ccc matches the actual sequence sss, Bob guesses the true outcome.
- In every position where ccc differs from sss, Bob guesses the opposite of the true outcome. In other words, Bob effectively “signals” exactly which positions differ between ccc and sss by guessing them incorrectly—and guesses them correctly wherever ccc and sss coincide.
- Alice always guesses the codeword.
Since Alice does not see the actual sequence, she sticks to the agreed codeword ccc for all 9 positions. She is simply guessing “the iii-th bit of ccc” each round. - At least 5 matches are guaranteed.
Because ccc differs from the actual sequence sss in at most 4 places, it matches in at least 9−4=59 - 4 = 59−4=5 places. In those matching positions: - ccc (Alice’s guess) = sss (the real toss),
- Bob is also guessing sss in those positions, so both are correct in at least 5 of the 9 rounds. Hence, no matter what the 9-heads/tails sequence is, this strategy guarantees at least 5 rounds where Alice and Bob both guess correctly.
Why this works (in a nutshell)
- You only “lose” points in positions where the chosen codeword ccc disagrees with the actual sequence sss.
- By design, there are at most 4 such disagreements.
- Bob chooses to sacrifice those at most 4 positions—he guesses them incorrectly on purpose (thus no point in those rounds)—but secures correctness in all the other 5 (or more) positions. The key is the covering radius of the code: you need a set of codewords so that every 9-bit string is within distance 4 of some codeword. Once you have that, the “both correct” count is at least 9−4=5.9 - 4 = 5.9−4=5.That is exactly the strategy that guarantees 5 wins out of 9.