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

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

- Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks by Persi Diaconis and Ron Graham, Princeton University Press.

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

- N. G. de Bruijn, Acknowledgement of Priority to C. Flye Sainte-Marie on the counting of circular arrangements of $2^n$ zeros and ones that show each $n$-letter word exactly once, T.H.-Report 75-WSK-06, (1975) Technological University Eindhoven.

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

- Donald E. Knuth, The Art of Computer Programming, Volume 4A, Combinatorial Algorithms: Part 1, Section 7.2.1.1.

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.

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