A red-backed deck is taken out and cut several times before being passed to an
audience member, who is invited to cut it further and then take off the top card.
A second person now takes the deck and removes the new top card. Two more people
do this, until four people have one card each. Request that the remainder of
the deck be thoroughly shuffled and given back to you. Have each person look at
their card and note its suit and value. Have the cards displayed in a face-down
row, in the order in which they were selected.
Say, "Let's identify the red cards first, which of you had a red card?" Pause,
while the corresponding audience members identify themselves. Joke, "Judging by
what I can see here," waving at the row of face-down red-backed cards, "I was
pretty sure you all had red cards!" Pause again, and then continue, "So,
which red card should I name first?" Point to the displayed row once
more, and as soon as somebody indicates a particular card, name it, and have it
turned over to confirm that your identification is correct. Continue with the
three remaining cards, in any order. You should score four out of four.
The light-hearted gag about red cards above is in fact crucial:
Without making it too obvious that you really need to know,
you find out which of the selected cards have red faces;
from knowledge of the red/black distribution alone, you can,
with sufficient preparation, tell what all four cards are.
Going Dutch (and Swedish)
We explain the principle underlying this mathemagical tour de force, which
goes back at least half a century,
with the kind permission of Persi Diaconis and Ron Graham, loosely following the
description they provide of related tricks and the associated mathematical
background in Products of Universal Cycles, a chapter of the new Martin
Gardner tribute book A Lifetime of Puzzles (AK Peters). That chapter, which
is highly recommended as it explores a great deal more material than we discuss
here, is, in turn, excerpted from the upcoming book, From Magic to
Mathematics--and Back (Princeton University Press), by the same authors.
The cards used are prearranged to start with, into a customized and memorized
circle of red/black values, which repeated cuts---and, if you can manage them,
false shuffles---do nothing to alter. The special sequence of reds/blacks
(think 0's and 1's), which cycles back on itself, has the property that no
subsequence of length four occurs more than once. Knowing which of the top four
cards are red allows you to deduce exactly what part of the circle had been
sampled, and assuming your memory is up to the task, or you use a cheat sheet,
you can then name all four selected cards correctly. For instance, if you know
that the cards in question are two reds followed by a black and then a red, then
there is only one possibility for the identities of the four cards in question.
The key ingredient here is binary de Bruijn sequences, named after the Dutch
mathematician who first published a paper on them in 1946. The longest possible
de Bruijn sequence for identifying k cards in a row as above clearly has
length 2^{k}. Graph theoretical considerations reveal that there
are 2^{2k - 1- k} distinct such maximal length sequences.
Small examples are easily constructed by hand. De Bruijn sequences of length
four and eight, for k = 2, 3, respectively, are given by
0 0 1 1
and
0 0 0 1 1 1 0 1.
The first is unique, and the second is one of two possibilities, the other being
the same sequence run in reverse. If we don't seek maximal length when k =
3, then 0 0 0 1 1 1 also works, in the sense that the six resulting "strings
of 3 in a row" are distinct (though we do not get 1 0 1 or 0 1 0 as strings).
There are sixteen de Bruijn sequences of length 16, corresponding to k =
4, one of which is given by
0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1.
Fans of 1970s Swedish pop music, who are also alphabetically inclined, may find
it easier to remember this last one converted to
AAAA BBBB ABBA ABAB,
which can, in turn, be morphed to
RRRR BBBB RBBR RBRB
for red and for black cards.
Though we do not use these in what follows, we note that there are 2048 binary
de Bruijn sequences of length 32, one of which is given by: 0000 0111 1101 1010
1110 0101 0011 0001. Note that the maximal runs of 0s & 1s need not be adjacent
in such sequences, as 0000 0101 0010 0011 1110 1110 0110 1011 works too.
A Two Role
The red-backed "deck" referred to at the start above is actually packet of 48
cards carefully assembled from parts of three identical regular red-backed decks.
Hopefully, nobody will notice that you're not playing with a full deck. The
"four shortened deck" you use consists of the same sixteen cards from three
normal decks, arranged the same way and stacked on top of one another, so that
the sixteen-card cycles of RRRR BBBB RBBR RBRB repeat.
Which sixteen cards? It's up to you! We invite readers to experiment here,
starting with something easy to remember---but not too "obvious," bearing in
mind that four in a row will end up exposed to view---perhaps alternating
Diamonds & Hearts and Clubs & Spades within the subsequences of reds and blacks.
More sophisticated selections can lead to additional magic possibilities. Once
you have committed a particular sequence of sixteen cards to memory, assemble
three such packets, taken from three identical red-backed decks,and stack them
to form a 48-card ``deck,'' then proceed as above.
Truer Purpose
Instead of basing the trick on the distribution of red and black cards, one could
rework it so that it's based on one suit, e.g., Clubs, versus the others. Then
you can say, "Let's start with the Clubs, who's got those?"---an innocent enough
sounding comment which serves its information-fishing purpose well. Once the
spectators with Clubs are known, then everything is known. You can identify
those Clubs followed by the other cards in any desired (suit) order. Being able
to say things like, "Let's move on to Diamonds, yes, that would be you, madam.
You must have the King of Diamonds," gives an appropriate (and totally correct!)
impression that you are all-knowing. For such a trick, each cycle of sixteen
cards must of course consist of eight Clubs and eight non-Clubs.
Some ambitious readers may wish to work with 32 = 2^{5} cards, and five
audience members; however neither 32 nor 64 = 2 x 32 is close enough to 52 for
comfort, so any pretense at using a full deck is out of the question. Diaconis
& Graham provide details of a maximal de Bruijn sequence of length 64 =
2^{6}, which is then cut down to one of length 52, which can be used for
an associated card trick using six spectators.
Dancing Queen
If the thought of remembering a string of sixteen card values and suits, not to
mention the corresponding red/black distributions, is too daunting, you may wish
to scale things down to the unique (up to reversal) de Bruijn sequence 0 0 0 1 1
1 0 1 of length 8, in its R R R B B B R B incarnation.
For values, try the 8 5 4 1
7 6 3 2, of the g4g8 bracelet
in the June 2008Card Colm, but with different suits from those
found there, to get what we hereby dub the d4b8 bracelet:
Remembering [8 5 4 1 7 6 3 2] is easy: think of the displayed circle of cards as
a capital omega (Ω), bringing to mind the word "alphabetical." Eight,
Five, Four, One, Seven, Six, Three, Two are indeed in that order. The suits
are not hard to remember either, as Diamonds & Hearts alternate within the reds,
as do Clubs & Spades within the blacks.
Using an ordinary blue-backed deck, place such a stack, starting with the
8♥, on top of the rest of a deck, keeping it there
throughout some fair-seeming shuffling, and deal the stack into a face-down circle.
Now, explain that three people must pick adjacent cards to represent partners for
a dancing Queen: ask somebody to fan through the remainder of the deck and pull
out the Q♥. Have this card placed face-up in the
middle of the circle of eight cards.
Turn away, while three adjacent cards in the circle are peeked at by different
spectators. Have these three cards, representing dancing partners, lined up in
order in front of the Queen, while the other five cards are shuffled back into
the deck. Turn back, and explain that each card/partner has a net worth, which
is indicated by its numerical value. Remind people that Aces are worth 1, Jacks
11, and so on, which adds to the illusion that any cards could be involved.
Furthermore, red cards are trustworthy as dancing partners, for a red Queen, but
black ones are not.
Have the Q♥ turned face-down too, and ask the
three participants to move their cards around along with the Queen, to simulate
three partners dancing with her. Say that having seen them dance, you now know
their identities. Just to check, give your participants a choice: either they
will reveal to you the total worth of the selected partners, by summing the three
card values while you turn away again, or they will indicate which partners are
trustworthy. Regardless of whether you are given the value sum or learn which of
the three cards are red, say, "Just as I thought," and proceed to identify all
three cards correctly.
In the first case, use the technique explained in the
June 2008Card Colm, not forgetting that the suits above
differ from the ones used there. In the second case, you can deduce which part
of the RRRBBBRB cycle, and hence the d4b8 bracelet, was sampled, from the
red/black distribution alone.
Other Founders
There is a considerable magic literature on applications of de Bruijn sequences,
both binary and more general ones, which has been and will likely remain mostly
invisible to outsiders. It is no exaggeration to say that entire books have been
written on the subject, featuring innovative applications and generalizations of
what we've considered. Pioneers from decades past include Bob Hummer, Larsen &
Wright, Ron Wohl, Max Maven and Leo Boudreau. The roots of the subject can be
traced back to Charles Jordan's "Coluria" from 1919.
Just as we have only revealed the tiniest tip of the magic iceberg above, we have
also only skimmed the surface of the many fascinating mathematical possibilities
discussed in the Diaconis & Graham chapter of
A
Lifetime of Puzzles (AK Peters), which explains magic ways to combine
universal cycles, far-reaching generalizations of de Bruijn sequences
first considered by Fan Chung along with Diaconis & Graham in 1992. Readers
hungry for more knowledge and inspiration (as well as open problems) are
strongly encouraged to start there.
Colm Mulcahy ([email protected])
completed his PhD at Cornell in 1985, under
Alex
F.T.W. Rosenberg. He has been in the department of mathematics at Spelman
College since 1988, and writing Card Colms---the only MAA columns to
actively encourage lying on a regular basis---bi-monthly since October 2004. For
more on mathematical card tricks, including a guide to topics explored in previous
Card Colms, see http://www5.spelman.edu/~colm/cards.html.
"A Two Role," "Truer Purpose" and "Dancing Queen" are anagrams of the titles of
well-known Abba songs. "Other Founders" is an anagram of "Four-Shortened."