Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

January 5, 2015

Mathematics and Magic: the de Bruijn Card Trick

Posted by Simon Willerton

A mathematician hands out a pack of cards to a group of five people. They repeatedly cut the deck and then take a card each. The mathematician tries to use telepathy to divine the cards that the people are holding but unfortunately due to solar disturbances, the mind waves are a bit scrambled and the mathematician has to ask a few questions to help unscramble the images being received. “Who had porridge for breakfast?” “Who is holding a red card?” “Is anyone a Pisces?” “Who has a dog called Stanley?” The answers to these questions are sufficient to allow the mathematician to name the card that each person is holding. The audience applaud wildly.

As  2d  5c  3s  6d

I learnt about this trick in a book I got for Christmas.

The first thing to note is that the authors are both respected mathematicians, so it is perhaps not surprising to learn that the mathematics involved is actually non-trivial. In my undergraduate course on Knots and Surfaces I do a few knot and rope tricks to enliven the lectures and to demonstrate some of the ideas in the course, but these are generally sleight-of-hand tricks unlike the tricks in this book which all have some interesting mathematics underlying them.

In this post I want to wear my mathematician’s hat and explain how the above card trick is based on the existence of de Bruijn sequences. Of course, if I were wearing my magician’s hat, I wouldn’t be allowed to reveal how the trick works!

The card trick

The alert amongst you will be guessing that the question “Who is holding a red card?” probably is the key, and indeed it is. The answer to this question contains five bits of information, so might be sufficient to identify one in 32 scenarios. Here’s the first sneaky part: the ‘deck’ only contained 32 cards.

The next sneaky part is that these 32 cards were arranged in an order such that the permutation of red and black cards amongst five consecutive cards uniquely identifies the five cards. The repeated cutting of the deck does not alter this cyclic order.

The final sneaky part is that the mathematician, being a mathematician, rather than memorising the order of the cards, has a cunning algorithm for turning the five bits of information into the suits and values of the five cards.

To explain all of this we need the idea of a de Bruijn sequence.

De Bruijn sequences

An order nn de Bruijn sequence on the letters {a 1,,a k}\{ a_{1},\dots , a_{k}\} is a cyclic string of k nk^{n} elements from the set {a 1,,a k}\{ a_{1},\dots , a_{k}\} such that each length nn string of kk letters occurs exactly once as consecutive letters in the string.

For example, 00110011 is a length 22 de Bruijn sequence on the letters {0,1}\{ 0,1\} , as it has 0000, 0101, 1010 and 1111 as its length 22 substrings — remember we are considering our string as being cyclic, so 1010 is obtained by cycling round to the beginning. However 01010101 is not such a de Bruijn sequence as, for instance, 0000 and 1111 are not substrings.

Here’s an order five sequence on two letters. 00000100101100111110001101110101 00000100101100111110001101110101 Each possible string of five letters occurs exactly once in this sequence.

The following theorem shows that such sequences always exist.

Theorem. For each nn and kk there are (k!) k n1/k n(k!)^{k^{n-1}}/k^{n} distinct order nn de Bruijn sequence on kk letters.

The sequences carry de Bruijn’s name because of a 1946 paper but the result he proved there on 22-letter sequences had already been proved, and forgotten, 50 years earlier by Flye Sainte Marie. The history is described in

Back to the card trick

Now we can convert our sequence of zeroes and ones to reds and blacks to give us a sequence of playing card colours such that in five consecutive cards the position of the red cards tell you where they come in the sequence. BBBBBRBBRBRRBBRRRRRBBBRRBRRRBRBR BBBBBRBBRBRRBBRRRRRBBBRRBRRRBRBR We can chose a sequence of cards which match this colour pattern, such as the following. 8c Ac 2c 4c As 2d 5c 3s 6d 4s Ah 3d 7c 7s 7h 6h \text {8c Ac 2c 4c As 2d 5c 3s 6d 4s Ah 3d 7c 7s 7h 6h} 4h 8h Ad 3c 6c 5s 3h 7d 6s 5h 2h 5d 2s 4d 8s 8d \text {4h 8h Ad 3c 6c 5s 3h 7d 6s 5h 2h 5d 2s 4d 8s 8d} Here, if it isn’t obvious, ‘A’ stands for ace, whilst ‘c’, ‘s’, ‘d’ and ‘h’ stand for the four suits clubs, spades, diamonds and hearts.

Actually my choice of cards for this sequence of colours was not random, but done so that each length five substring of reds and blacks encodes the first card in the corresponding subsequence of five cards. For instance, if we take the fifth substring, “BRBBR”, this is supposed to encode the fifth card, the ace of spades. We chose the cards to match the colour sequence, so the first B corresponds to colour of the ace of spades. The rest of the coding is similarly simple.

Let’s first convert the substring back to zeroes and ones, as that’s a more natural place to think mathematically: this means BRBBR becomes 01001. The first bit is the colour of the card, as we’ve already noted. The second bit together with the first bit will identify the suit, ordered alphabetically by colour: 00=clubs,01=spades,10=diamonds,11=hearts. 00 = \text {clubs},\;01 = \text {spades},\; 10 = \text {diamonds},\; 11 = \text {hearts}. The final three bits just encoded the card value modulo 8 in binary: 001=ace,010=2,011=3,,111=7,000=8. 001 = \text {ace},\; 010 = 2,\; 011=3,\;\dots ,\; 111=7,\;000 = 8. Thus 01001, or, BRBBR, gives the ace of spades.

All you need to do now to perform the card trick is take a pack of cards, throw out all of the nines, the tens and the royals, then order the remaining the cards as above. Next you need to memorize the order of these 32 cards(!!). Then you can pass round the cards allowing the audience to cut the deck, thus not altering the cyclic order. When the sequence of red and black cards is revealed to you, you can decode it to learn the first card, and your knowledge of the order allows you to say what the other four cards are as well.

We’ll now see a method that means that you don’t have to memorize the order, just memorize a simple mathematical procedure that can be used to recover the order.

Linear feedback shift registers

When the number of letters we are using is prime, some of the de Bruijn sequences can be generated by using so-called ‘linear feedback shift registers’. See

If we want to generate a single order nn sequence on the letters {0,1,k1}\{ 0,1,\dots k-1\} , where kk is prime, then we can pick an irreducible polynomial x nb nx n1b 2xb 1 k[x] x^{n}-b_{n}x^{n-1}-\dots - b_{2}x -b_{1}\in \mathbb{Z}_{k}[x] and an initial string of nn numbers s 1s ns_{1}\dots s_{n} which isn’t 0000000\dots 0. We can then define the next term in the sequence by s n+1b 1s 1+b 2s 2++b ns n k. s_{n+1}\coloneqq b_{1} s_{1} + b_{2}s_{2} +\dots +b_{n} s_{n}\in \mathbb{Z}_{k}.

For instance, we are interested in an order 55 sequence on 22 letters. We are going to use the polynomial x 5x 21x^{5}-x^{2}-1 which we observe is irreducible in 2[x]\mathbb{Z}_{2}[x]. We will start with the non-zero string 0000100001. The algorithm above tells us that the next term is the first term plus the third term mod 22, ie. 0+00+0, which is 00. So our sequence starts 000010000010.

We then repeat using s 2s 3s n+1s_{2}s_{3}\dots s_{n+1} as the string of nn letters, so iteratively we define s ib 1s in+b 2s in+1++b ns i1 k. s_{i}\coloneqq b_{1} s_{i-n} + b_{2}s_{i-n+1} +\dots +b_{n} s_{i-1}\in \mathbb{Z}_{k}. Provided that the polynomial we start with is irreducible this results in a sequence which will not repeat until after k n1k^{n}-1 terms, and every substring of nn letters with occur except the trivial one 00000\dots 0. Such a sequence is known as a punctured de Bruijn sequence.

Puzzle 1. Why is it necessary and sufficient that the polynomial is irreducible?

Going back to our example which started 000010000010 we find that the resulting punctured de Bruijn sequence is 0000100101100111110001101110101. 0000100101100111110001101110101.

Any punctured de Bruijn sequence can be made into a true de Bruijn sequence by simply adding an extra zero into the unique substring of n1n-1 zeroes. Doing that to the above sequence gives back the de Bruijn sequence we saw much earlier in this post.

Back to the card trick, again

Now we can incorporate the linear feedback shift register into the trick. When the order of red and black cards are revealed to you, for instance as BRBBR, you first translate to binary, 0100101001, and then to a card value, ace of spades, as before. The difference is that now you can calculate the next card rather than having to remember it.

You add the first and third bits together modulo 22, append that to the end of the string and forget the first bit. This gives you 1001010010 which is the two of diamonds, and you can check that this is indeed the next in the card sequence listed above! You repeat this to obtain the other three cards that are being held by members of the audience.

The astute amongst you will note that our linear feedback shift register algorithm only gives a punctured de Bruijn sequence, so would not include the substring 0000000000, which corresponds to the eight of clubs. There are two ways around this.

  • Either throw away the eight of clubs and perform the trick with just 31 cards,

  • or else remember that between the eight of diamonds 1000010000 and the ace of clubs 0000100001 comes the eight of clubs.

I hope you’ve seen how this trick involves some interesting mathematics and you can now go and amaze your friends. I’ll leave you to find out what other interesting applications de Bruijn sequences have. I haven’t got very far in the book of Diaconis and Graham yet, but I’m hoping that it’s all as fun as the bits I’ve read so far.

Posted at January 5, 2015 7:36 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2798

8 Comments & 0 Trackbacks

Re: Mathematics and Magic: the de Bruijn Card Trick

A neat trick - it looks like a good book.

I’d just been talking to my son about Graham’s number (of all things), and the next thing I happened to read was your article. I read the whole post and it wasn’t until I reached the end that I realised that the co-author of this book was a Graham too.

Any relation? I wondered. I clicked on the link and … its the same guy!!

Posted by: Colin Backhurst on January 5, 2015 11:30 PM | Permalink | Reply to this

Re: Mathematics and Magic: the de Bruijn Card Trick

Absolutely the same Graham! But that Graham’s number has an odd history: it was first touted (in Martin Gardner’s old Mathematical Games column) as the largest number that has ever cropped up in serious mathematics research, but it turns out it wasn’t – it was only something invented by Graham during an interview with Gardner to illustrate a large upper bound of a number arising in Ramsey theory, which actually has a much lower upper bound. I think Graham thought it would be much easier to describe to Gardner, not the actual upper bound that he published, but this other thing which come to be known as Graham’s number, and still be sure he wasn’t saying anything wrong (since Graham’s number does which he said: gives an upper bound to the Ramsey theory problem).

But this story only came out somewhat recently, when our host John Baez, not finding where this Graham’s number comes up in research, finally just asked Graham what was the deal, and that’s what Graham told him. I just checked and the story is told in Wikipedia, and John reported it here.

Posted by: Todd Trimble on January 6, 2015 12:49 AM | Permalink | Reply to this

Re: Mathematics and Magic: the de Bruijn Card Trick

That same (Ron) Graham has an 80th birthday conference coming up in June.

Posted by: Allen Knutson on January 6, 2015 3:44 AM | Permalink | Reply to this

Re: Mathematics and Magic: the de Bruijn Card Trick

I am a magician with a BA in Math. While the math is great where is the trick? - Perhaps dyou could explain about the choosing of the cards and what the mystery in the way you reveal the chosen cards, because the average spectator is not going to be awed by a “memorized stacked deck routine” no matter whether you actually memorize your stack of 32 cards, or whether you are using binary to calculate the next card from the previous. Please help me understand where the drama is as a magic trick. The truth is that as you have so far discussed it, this trick will fall flat on its face - please explain how pigrnerform it so that it is not boring

-Ronald Levy

Posted by: Ronald Lyev on February 3, 2015 3:14 AM | Permalink | Reply to this

Re: Mathematics and Magic: the de Bruijn Card Trick

If you’re a magician with a mathematical background I’m sure you’d enjoy Diaconis and Graham’s book. You should have a look and see how they describe the performance. Being a proper magician, you’re likely to have more of a feel than me for where to insert the misdirection and how to put in appropriate patter.

You say that the audience won’t be impressed by you just having learnt the order of the deck, but you have done considerably more than that, namely put the pack in an order that makes five cards identifiable by the position of the red cards. This is, naturally, the kind of thing that you don’t want your audience to cotton on to though. For instance, it would make sense not to reveal the cards in the obvious order, then it would be more likely to be clear that you know the order of the deck. Diaconis and Graham suggest getting the people with red cards to stand up so you can identify their cards first.

I’ve only done the trick a couple of times to close friends, so haven’t quite developed my own banter around it. Diaconis and Graham say they’ve had much success with it. There’s a few bits of interesting mathematics in the book that they say should be the basis of some good tricks and they leave it as an exercise to create the tricks.

Posted by: Simon Willerton on February 4, 2015 9:48 AM | Permalink | Reply to this

Re: Mathematics and Magic: the de Bruijn Card Trick

I am a magician with a BA in Math. While the math is great where is the trick? - Perhaps dyou could explain about the choosing of the cards and what the mystery in the way you reveal the chosen cards, because the average spectator is not going to be awed by a “memorized stacked deck routine” no matter whether you actually memorize your stack of 32 cards, or whether you are using binary to calculate the next card from the previous. Please help me understand where the drama is as a magic trick. The truth is that as you have so far discussed it, this trick will fall flat on its face - please explain how pigrnerform it so that it is not boring

-Ronald Levy

Posted by: Ronald Lyev on February 3, 2015 3:15 AM | Permalink | Reply to this

Re: Mathematics and Magic: the de Bruijn Card Trick

Happy New Year! I didn’t know you had a magician’s hat.

Posted by: John Baez on January 7, 2015 9:26 PM | Permalink | Reply to this

Re: Mathematics and Magic: the de Bruijn Card Trick

Yes, but I don’t wear it all the time, and it’s probably not as cool as a wizard’s hat.

Posted by: Simon Willerton on January 9, 2015 5:09 PM | Permalink | Reply to this

Post a New Comment