Magic Cards That Catch a Lie

What’s going on

Think of a number from 0 to 31 and tell the scene above, card by card, whether your number is on it. Press Read my mind. The trick is to add the first number of every card you said yes to. The first numbers are 16, 8, 4, 2 and 1, and every number from 0 to 31 is a sum of some of them, in exactly one way: 22 is 16 + 4 + 2, 7 is 4 + 2 + 1.

That is binary. Your yes and no answers are the binary digits of your number: yes, no, yes, yes, no is 1 0 1 1 0, which is 22. Card 1 holds every number whose binary form has a 1 in the sixteens place, card 2 every number with a 1 in the eights place, and so on. Five yes-or-no questions are enough because 2 × 2 × 2 × 2 × 2 = 32.

Skipping a card

Switch the scene to 6 cards, skip one. The sixth card holds every number that appears on an odd number of the first five cards. So every number now appears on an even number of cards: 22 is on cards 1, 3 and 4, and on card 6 as well, four cards in all.

Now you may refuse to answer one card, and the trick still works. Count the yeses you did give. If the count is odd, the missing answer must be yes; if even, it is no. This extra card is a parity check, and computers use the same idea to notice when a bit has been garbled.

It cannot do more, though. If you lie about a card instead of skipping it, the number of yeses becomes odd, so the trick knows something is wrong, but not which card.

Lying once

Choose 7 cards, lie once. The numbers go from 1 to 15. The first four cards are the binary cards with first numbers 8, 4, 2, 1. The other three are check cards, and every card has a three-digit code printed in blue at the bottom: all seven codes are different and none is 000.

The check cards are filled so that, for honest answers, the codes of the yes cards always add up (digit by digit, without carrying) to even digits. Take 13: it is on cards 1, 2, 4 and 7, with codes 011, 101, 111 and 001. The columns add up to 2, 2 and 4, all even.

Now suppose you lie about card 2 and say no. The yes codes are 011, 111 and 001: the columns add to 1, 2, 3. A lie moves one card from one pile to the other, which changes the column sums by exactly that card’s code. So the odd columns spell out the code of the lie: odd, even, odd is 101, card 2. Flip that answer back, add 8 + 4 + 1, and you get 13. Press Random volunteer in the scene to watch it catch lies again and again.

Why seven cards?

With four honest answers there are 16 possible numbers. A volunteer who may lie once can produce, for each number, 8 different patterns of answers: the honest one, or a lie on any one of the 7 cards. 16 × 8 = 128, and seven cards give exactly 2⁷ = 128 patterns. Not one pattern is wasted. This set of cards is the famous Hamming code.

Try it yourself

1. Make the birthday cards

Which cards of the 0 to 31 trick hold the number 27?

Answer

27 = 16 + 8 + 2 + 1, which is 11011 in binary. So it is on cards 1, 2, 4 and 5, and not on card 3 (the fours card).

2. A missing answer

With the six cards, a friend says yes to cards 1, 2 and 5, no to cards 4 and 6, and refuses to answer card 3. What is the number?

Answer

Three yeses is odd, so card 3 is a yes. Then the first five answers are yes, yes, yes, no, yes: 16 + 8 + 4 + 1 = 29. Check: 29 is on four of the six cards, an even number.

3. Too much for one lie

Why can’t three check cards protect numbers from 0 to 31 against one lie?

Answer

32 numbers would need five data cards, eight cards in all. Each number then has 1 + 8 = 9 possible answer patterns, and 32 × 9 = 288 patterns are needed, but eight cards give only 2⁸ = 256. With four check cards (nine cards, 512 patterns) it can be done.

Go deeper

• Richard Hamming invented these codes at Bell Labs around 1950, reportedly after a weekend in which a relay computer kept stopping on errors it could detect but not fix.
• Error-correcting codes that grew from this idea protect the memory chips in servers and the pictures sent back by space probes. QR codes use a stronger relative that still reads when part of the code is torn off.