## 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.

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 $n$ de Bruijn sequence on the letters $\{ a_{1},\dots , a_{k}\}$ is a cyclic string of $k^{n}$ elements from the set $\{ a_{1},\dots , a_{k}\}$ such that each length $n$ string of $k$ letters occurs exactly once as consecutive letters in the string.

For example, $0011$ is a length $2$ de Bruijn sequence on the letters $\{ 0,1\}$, as it has $00$, $01$, $10$ and $11$ as its length $2$ substrings — remember we are considering our string as being cyclic, so $10$ is obtained by cycling round to the beginning. However $0101$ is not such a de Bruijn sequence as, for instance, $00$ and $11$ are not substrings.

Here’s an order five sequence on two letters. $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 $n$ and $k$ there are $(k!)^{k^{n-1}}/k^{n}$ distinct order $n$ de Bruijn sequence on $k$ letters.

The sequences carry de Bruijn’s name because of a 1946 paper but the result he proved there on $2$-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$ We can chose a sequence of cards which match this colour pattern, such as the following. $\text {8c Ac 2c 4c As 2d 5c 3s 6d 4s Ah 3d 7c 7s 7h 6h}$ $\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 = \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 = \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 $n$ sequence on the letters $\{ 0,1,\dots k-1\}$, where $k$ is prime, then we can pick an irreducible polynomial $x^{n}-b_{n}x^{n-1}-\dots - b_{2}x -b_{1}\in \mathbb{Z}_{k}[x]$ and an initial string of $n$ numbers $s_{1}\dots s_{n}$ which isn’t $000\dots 0$. We can then define the next term in the sequence by $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 $5$ sequence on $2$ letters. We are going to use the polynomial $x^{5}-x^{2}-1$ which we observe is irreducible in $\mathbb{Z}_{2}[x]$. We will start with the non-zero string $00001$. The algorithm above tells us that the next term is the first term plus the third term mod $2$, ie. $0+0$, which is $0$. So our sequence starts $000010$.

We then repeat using $s_{2}s_{3}\dots s_{n+1}$ as the string of $n$ letters, so iteratively we define $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^{n}-1$ terms, and every substring of $n$ letters with occur except the trivial one $00\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 $000010$ we find that the resulting punctured de Bruijn sequence is $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 $n-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, $01001$, 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 $2$, append that to the end of the string and forget the first bit. This gives you $10010$ 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 $00000$, 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 $10000$ and the ace of clubs $00001$ 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

### 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