Five Colours, Five Cards
You cut a face-down packet as often as you like and deal five cards to five people. They tell me only whether each card is red or black, and I name all five.
Watch the lectureLecture 13 · Five colours reveal five cards
Try it
You are all five spectators. Cut the packet, deal five, look at your cards, and report only their colours. Cuts only: no shuffling.
Why it works
The packet was arranged in advance, and the arrangement does all the work. There are no marked cards and no glimpses of a face.
Write 0 for a black card and 1 for a red card. Then five colour reports make a word of five bits, such as 01001. How many such words are there? Two choices for the first card, two for the second, and so on: 2 × 2 × 2 × 2 × 2 = 32. The packet has exactly 32 cards.
The prepared order makes sure that wherever you cut, the five colours you report form a word that no other cut produces. So your report is an address. It tells me where in the packet your five cards sit, and I read their names off my list. I am not guessing five cards; I am solving one location problem.
Why don’t your cuts spoil the arrangement? A cut moves a block from the top to the bottom without mixing either block. Lay the packet in a circle and a cut only changes where we start reading: every card keeps the same neighbour after it. Five cards that run off the end of the written list simply continue at its beginning.
Every run of five neighbouring cards around the circle shows a different colour pattern, so five colours point to exactly one place in the circle.
Where does such a circle come from?
Finding an arrangement like this by trial and error is hopeless. The last step above shows the way in. Neighbouring windows overlap: move on one card and you drop the first bit, keep four, and gain one. So treat each four-bit overlap as a place to stand, and each five-bit word as an arrow from its first four bits to its last four. The word 01001 is an arrow from 0100 to 1001.
Walking along an arrow is moving the window on by one card. A circle that shows every word exactly once is then a closed walk that uses every arrow exactly once. Such a walk is called an Euler tour. You may pass through a place many times; it is the arrows, the words, that must each be used once.
A finite directed graph has an Euler tour when two things hold: at every place, as many arrows come in as go out; and from any place you can reach any other. Here both are easy to see. From every context there are two arrows out (append 0 or append 1) and two arrows in (put 0 or 1 in front). And you can reach any context by appending its bits one at a time. So circles like ours exist for windows of every length.
Try it on the small version: windows of three colours, four two-bit contexts, eight word-arrows, including two loops.
Challenge
Each packet below has been damaged by a swap. Swap cards until both checks pass: every cut gives a different colour word, and the original lookup sheet names the right five cards for every cut.
Perform it yourself
Set-up
- Take the aces through eights of all four suits: 32 cards.
- Arrange them face down in exactly this order, top card first:
- Lay out five numbered places in a row, place 1 on the spectators’ left as they look at the table.
- Keep the lookup sheet (below) where you can read it. While you are learning, it is fine to use it openly.
Performance
- Explain the one rule: you may cut, but not shuffle. A cut means lift a block from the top, put it on the table, and put the rest of the packet on top of it.
- Let several people cut, each choosing the size of the block. Keep your hands away.
- Have the top card dealt to place 1, the next to place 2, and so on to place 5. Deal them separately, one per place: dealing them into one pile would reverse their order.
- Each person looks at their own card privately and remembers its value and suit.
- Starting at place 1, ask only for colours: black or red. Repeat the report back before you name anything.
- Turn the report into bits (black 0, red 1), find that word on the sheet, and name the five cards in place order. Ask each person to show their card as you name it.
Things to watch
- A wrong colour report cannot be detected. Every five-bit word is a valid address, so a mistake leads to a confident wrong answer. If anyone is unsure, ask them to look again before the reveal.
- If someone shuffles, or the five are taken from different places, the guarantee is gone. Say so, and reset the packet openly.
- Before another round, put the five cards back on top in their order: the card from place 5 on the packet first, then 4, 3, 2, and finally place 1’s card on top. The circle is then exactly as it was, merely cut. If in doubt, rebuild the packet from the list.
- Practise with the faces visible first: cut, read five colours, find the row, check all five names. Accuracy comes before speed.
The lookup sheet (32 rows, in binary order)
| Colours, places 1→5 | Cards at places 1, 2, 3, 4, 5 |
|---|
Going deeper
Why 32 cards, and not a full deck?
Five colour reports give at most 25 = 32 different words. If a packet had 33 or more starting places, two of them would have to share a report, however cleverly it was arranged, and nothing could tell those two apart. With 52 cards and five reports the trick cannot work. A longer report, a richer observation (suits, say) or fewer starting places would change that count.
Counting only gives the limit. It does not make an arrangement that reaches it: a badly ordered 32-card packet could repeat a few words over and over. That is why the full check, all 32 windows, matters.
Removing a card is not harmless
Take the eight-bit circle 00011101, whose eight three-bit windows are all different. Delete its last bit and join the ends: 0001110. Its windows are 000, 001, 011, 111, 110, 100 and then 000 again, at the new join. The word 000 now occurs at the first and the seventh start, and a report of 000 could mean either. Any change to the circle creates new windows around the change, and those need checking too.
The packet names its own cards
This particular order has a second secret, from Diaconis and Graham. Read a card’s own window of five bits as two suit bits (00 clubs, 01 spades, 10 diamonds, 11 hearts) followed by a three-bit rank (001 is the ace, 010 is two, …, and 000 stands for eight). The window that starts at the A♠ is 01001: suit 01, spades; rank 001, ace. That works for all 32 cards.
The next window is made by a rule: drop the first bit and append the first bit plus the third, where 1 + 1 counts as 0. From 01001 that gives 10010, the 2♦, then 00101, the 5♣, and so on. So a performer can name the cards by calculation instead of a sheet. Two links need special care: the plain rule never reaches 00000 (the 8♣), so this 32-card version sends 10000 to 00000 and 00000 to 00001 by hand.
How many such circles are there?
For windows of three there are exactly two binary circles, 00011101 and 00010111, if we do not care where we start reading. For windows of four there are 16, and for windows of five there are 2,048. In general there are 22k−1 − k for windows of length k. Different Euler tours of the same graph give different circles.
The cycles are named after Nicolaas de Bruijn, who counted them in 1946. The count had already been found by Camille Flye Sainte-Marie in 1894.
Sources
Persi Diaconis and Ron Graham, Magical Mathematics (Princeton, 2012), chapter 2, pp. 18–25: the prepared 32-card packet, its lookup, the de Bruijn graph and its Euler tours; pp. 26–29 for the shift-register naming rule. Presented here with five numbered places so the reading order is unambiguous.
Colm Mulcahy, Mathematical Card Magic: Fifty-Two New Effects (CRC Press, 2013), chapter 10, pp. 252–256: smaller colour-pattern packets and card adaptations.