Card Colm
(by Colm Mulcahy)

December 2008

What's Black and Red and Red All Over?

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 2k. Graph theoretical considerations reveal that there are 22k - 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 = 25 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 = 26, 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 2008 Card 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 2008 Card 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 (colm@spelman.edu) 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."

Past Columns