The n-Category Café

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.