# A Magic Trick and Applications of De Bruijn Sequence

*Brian Li*

*2020-06-03*

*MAT388 De Bruijn Sequence Mathematics*

## # A Magic Trick for Five Participants

This magic trick is first introduced in "Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks" by Persi Diaconis and Ron Graham.

Let us begin by introducing this trick from the audiences' perspective. A magician starts the trick by asking five random volunteers to participate. The deck will be passed between the five volunteers and each volunteer will cut the deck. When the deck is cut by the last(5th) volunteer, the magician asks the 5th volunteer to take the top card then pass it back to the 4th volunteer. The 4th volunteer will repeat the same process until every volunteer has a card in their hand. The magician states that he can guess all five cards if given some additional information about the volunteers, then he or she asks, "Would all of you with a red card please stand up?" Volunteers holding a red card would then stand up accordingly. The magician proceeds to name all five cards correctly, including the number and the suit.

Now we will describe the same magic trick from the magician's perspective. The deck is pre-arranged with some very special properties and only has 32 cards in it, which we will discuss in detail below. When volunteers cut the deck, these properties are preserved. After all five volunteers have cut the deck and received their card, the magician starts to ask multiple questions. However, the only important question is that "Who has the red card?". The magician will utilize the special properties of the deck: these 52 cards are arranged in an order such that **the sequence of red and black cards amongst five consecutive cards uniquely identify the five cards**. Therefore by knowing who has the red card, the magician can tell exactly what these 5 cards are since it exist uniquely in the deck. To explain why this is possible, we hereby introduce the idea of a De Bruijn sequence.

## # De Bruijn Sequence

**Definition**: A de Bruijn sequence is a cyclic sequence of a given alphabet

**Example 1.0:**
Let us produce the de Bruijn sequence for

**Example 1.1:**
Let us produce the de Bruijn sequence for

**Application in the magic trick:**
In our magic trick, we have

**Step 1:** Select

**Step 2:** Now we need to construct the de Bruijn deck. Thanks to example 1.1, we have already obtained such sequence

I have randomly picked

**Step 3**: Get ready to perform your trick! You can either memorize the order, or prepare a small cheat sheet. Here is a sample cheat sheet that I have provided for you:

Color Order | Corresponding Cards |
---|---|

Now by using this cheat sheet, you can perform the trick to a large number of audiences.

## # Generalizations and Variations

**One variation is to change the value of k**. In a deck of cards if we distinguish element in a set by number, then there are only two options black and red. However, what if we distinguish by number? We could ask who has the highest card, the second highest, and the third highest? That gives us. What if we use some other characteristics? What if we are not using standard 52-card deck? What if we use the deck from Uno? Or set? **Another variation is to change the value of n**. By changing the length of the subsequece, we should be able to change the number of cards to use to perform this trick. For,we are using , what happened if we use ? How many cards would we need?

We hereby provide some properties of the de Bruijn sequence to help the readers to further generalize the trick.

**Theorem 1**: The number of distinct de Bruijn sequences

**Theorem 2**: The length of a de Bruijn sequence

**Proof**: We agree that the length of