The mind reader who survives a lie
Helpful first: the four-card trick in Counting to 31 on one hand. Ready if you can say which of 8, 4, 2, 1 add up to 13.
Tonight's idea
You already know the ordinary version of this trick from Counting to 31 on one hand. Four cards, one for each binary digit, and the four yes/no answers spell the number in binary. But if the person lies on one card, you get the wrong number and never know it.
The fix is to add three checking cards. Here are all seven. Cut them out or just point at them.
Cards 3, 5, 6 and 7 are the old binary cards: the 8s, 4s, 2s and 1s. Cards 1, 2 and 4 are new. Write each "yes" as a 1 and each "no" as a 0, in card order, and you get a string of seven bits.
The cards are built so that, if nobody lies, three checks all come out even:
Check B: cards 2, 3, 6, 7 have an even number of yeses.
Check C: cards 4, 5, 6, 7 have an even number of yeses.
Look at which cards are in each check. Check A is every card whose number has a 1 in the ones place (1, 3, 5, 7). Check B is every card with a 1 in the twos place (2, 3, 6, 7). Check C is every card with a 1 in the fours place (4, 5, 6, 7). Card 1 is only in check A, card 2 only in B, card 4 only in C, and card 7 is in all three.
Suppose exactly one answer is a lie, on card \(k\). It breaks exactly the checks that card \(k\) belongs to, and those checks are the binary digits of \(k\). So the failed checks spell out the lying card:
2. Flip that answer.
3. Read cards 3, 5, 6, 7 as 8s, 4s, 2s, 1s and announce the number.
This is a Hamming code, invented by Richard Hamming in 1950 because his computer kept crashing at weekends over single wrong bits.
Watch one
Someone thinks of 13. Honestly, 13 is on cards 1, 3, 5, 7 and not on 2, 4, 6, so the true answers are \(1\,0\,1\,0\,1\,0\,1\). But they decide to lie on card 5 and say "no". You hear \(1\,0\,1\,0\,\mathbf{0}\,0\,1\).
| Check | Cards | Yeses | Even? | Score |
|---|---|---|---|---|
| A | 1, 3, 5, 7 | 1+1+0+1 = 3 | no | 1 |
| B | 2, 3, 6, 7 | 0+1+0+1 = 2 | yes | 0 |
| C | 4, 5, 6, 7 | 0+0+0+1 = 1 | no | 4 |
Total \(1 + 0 + 4 = 5\). "You lied on card 5." Flip it back to yes. Now cards 3, 5, 6, 7 read \(1, 1, 0, 1\), which is \(8 + 4 + 0 + 1 = 13\). "Your number is 13."
Try the same number with no lie: \(1\,0\,1\,0\,1\,0\,1\). Check A: \(1+1+1+1 = 4\), even. Check B: \(0+1+0+1 = 2\), even. Check C: \(0+1+0+1 = 2\), even. Total 0. "You told the truth, and your number is 13."
Your turn
Tonight's core: the example and exercises 1 and 2. The rest can wait for another visit.
- Encode. For each secret, write the seven honest answers as bits in card order. Use the cards, then check that all three checks come out even. Secrets: 11, 6, 0, 15.
- Decode, one lie allowed. Here are the answers you heard. Find the lie (if any) and the secret.
(a) \(1\,0\,1\,0\,0\,1\,0\) (b) \(1\,1\,1\,0\,0\,1\,1\) (c) \(1\,1\,0\,0\,1\,1\,1\) (d) \(0\,0\,1\,1\,0\,0\,1\) - Someone answers "no" to every card except card 5. Which card did they lie on, and what is their number? (Think before you compute: what happens if the lie is on a checking card?)
- Why is card 7 in all three checks, while card 1 is only in check A? Write the numbers 1 to 7 in binary and explain in one sentence.
- Build card 2 yourself, without looking. Card 2 must make check B come out even, and check B contains cards 2, 3, 6, 7. So a number is on card 2 exactly when it is on an odd number of the cards 3, 6, 7. Work through 0 to 15 and compare with the printed card.
Hint
Take 11: is it on card 3? Card 6? Card 7? Three yeses, an odd count, so 11 goes on card 2. - Perform the trick on someone. Do it three times, once with no lie. Record your hits and misses honestly. If you missed, redo the three checks and find your slip.
Let the computer read your mind, then see how it does it, at mathdetours.com/demos/hamming.html. It also shows what happens with two lies.
Stretch: why one lie is the limit
There are 16 secrets. For each secret there are 8 things you might hear: the honest string, or one of 7 strings with a single lie. That makes \(16 \times 8 = 128\) possible strings you could hear. How many strings of seven bits are there altogether? What does that tell you?
The answer means the 128 "one lie or none" strings use up every seven-bit string, with none to spare. So if someone lies twice, the string they produce is already claimed by some other secret with one lie, and the method will confidently name the wrong number. Try it: take the honest string for 5, which is \(0\,1\,0\,0\,1\,0\,1\), flip cards 2 and 6, and decode. What number does the trick announce, and which card does it blame?
Computer memory, hard drives, QR codes and spacecraft all use codes like this. A QR code can lose up to 30% of its squares (that is why people can print logos in the middle) and still scan, using a bigger cousin of tonight's idea. The question engineers ask is always the same: how many extra checking bits buy how many corrected mistakes?
Answers
- 11 is on cards 2, 3, 6, 7: \(0\,1\,1\,0\,0\,1\,1\). 6 is on cards 1, 2, 5, 6: \(1\,1\,0\,0\,1\,1\,0\). 0 is on no card: \(0\,0\,0\,0\,0\,0\,0\). 15 is on every card: \(1\,1\,1\,1\,1\,1\,1\). In each case A, B and C are even (for 15 every check has four yeses).
- (a) A: \(1+1+0+0 = 2\) even; B: \(0+1+1+0 = 2\) even; C: \(0+0+1+0 = 1\) odd. Score 4: the lie is on card 4. Cards 3, 5, 6, 7 read 1, 0, 1, 0, so the secret is \(8 + 2 = 10\).
(b) A: \(1+1+0+1 = 3\) odd; B: \(1+1+1+1 = 4\) even; C: \(0+0+1+1 = 2\) even. Score 1: the lie is on card 1, a checking card, so the secret is unaffected. Cards 3, 5, 6, 7 read 1, 0, 1, 1: secret \(8 + 2 + 1 = 11\).
(c) A: \(1+0+1+1 = 3\) odd; B: \(1+0+1+1 = 3\) odd; C: \(0+1+1+1 = 3\) odd. Score \(1+2+4 = 7\): the lie is on card 7. Flip it to 0; cards 3, 5, 6, 7 read 0, 1, 1, 0: secret \(4 + 2 = 6\).
(d) A: \(0+1+0+1 = 2\); B: \(0+1+0+1 = 2\); C: \(1+0+0+1 = 2\). All even, score 0, no lie. Cards 3, 5, 6, 7 read 1, 0, 0, 1: secret \(8 + 1 = 9\). - Heard \(0\,0\,0\,0\,1\,0\,0\). A: 1 yes, odd, score 1. B: 0, even. C: 1 yes, odd, score 4. Total 5: they lied on card 5. The honest answers were all "no", so the secret is 0. (A single yes can never be honest, because every number except 0 is on at least three cards.)
- In binary, 1 = 001, 2 = 010, 3 = 011, 4 = 100, 5 = 101, 6 = 110, 7 = 111. A card belongs to check A, B or C when its number has a 1 in the ones, twos or fours place, so 7 = 111 is in all three and 1 = 001 is only in check A. That is exactly why the failed checks spell out the lying card's number.
- Card 3 holds 8–15, card 6 holds 2, 3, 6, 7, 10, 11, 14, 15, card 7 holds the odd numbers. Counting memberships: 0 (0 cards), 1 (1: card 7), 2 (1: card 6), 3 (2), 4 (0), 5 (1: card 7), 6 (1: card 6), 7 (2), 8 (1: card 3), 9 (2), 10 (2), 11 (3), 12 (1: card 3), 13 (2), 14 (2), 15 (3). Odd counts: 1, 2, 5, 6, 8, 11, 12, 15. That is card 2.
- If a performance failed, the usual slips are counting a check with the wrong cards, or forgetting to flip the lie before reading off the number.
Stretch. There are \(2^7 = 128\) strings of seven bits, exactly the number of "one lie or none" strings. So the 16 secrets, each with its ball of 8 nearby strings, tile the whole space perfectly with no overlap and no gaps. Two lies: 5 is \(0\,1\,0\,0\,1\,0\,1\); flipping cards 2 and 6 gives \(0\,0\,0\,0\,1\,1\,1\). A: \(0+0+1+1 = 2\) even. B: \(0+0+1+1 = 2\) even. C: \(0+1+1+1 = 3\) odd. Score 4, so the trick blames card 4 and flips it, giving \(0\,0\,0\,1\,1\,1\,1\), and reads cards 3, 5, 6, 7 as 0, 1, 1, 1: it announces 7. Wrong number, wrong card, and no warning. One extra check bit (an eighth card listing the numbers on an odd number of the other seven) would at least detect that two lies happened.