De Brujin Card Trick

Cut a prepared deck of 48 cards as many times as you want. Let a group of 4 people take a card each. Start asking questions of any kind. Favourite US president? Who likes black olives? Somewhere in there, slip in the question “Who is holding a red card?”. You can then, magically, name every card that each person took (value and suit).

The following trick was sourced from Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks by Persi Diaconis and Ron Graham.

Similar to the Si Stebbins stack, the 16 cards are in a cyclic order. This means that regardless of how the deck is cut, the overall order is not changed. It is important that you do not shuffle the cards in a way that would change this order, such as riffle shuffling (weaving two halves of the deck) or the trick will not work.

A “substring” of cards is a sequence of cards taken from a larger string of cards. In a de Brujin sequence, every possible permutation of cards in a substring (length n) occurs exactly once. The “alphabet size” refers to the number of distinct elements (in this case card-colours) in a sequence. We represent the alphabet size with “k”. In our case, let red cards be “R” and black cards be “B”- making an alphabet of {R,B} (size k=2). If we set the substring size to length n=2, then RRBB is a de Brujin sequence, as the substrings RR, RB, BR, and BB all occur just once (with BR occuring when the sequence loops back to the beginning). We denote this set using B(k,n), which for this example would be B(2,2).

A de Brujin sequence will have k^n symbols; 2^2=4.

Since 4 cards are being taken, we say that the sequence has an order of 4. A de Brujin sequence B(2,4) would look like:
BBBB RRRR BRRB BRBR

You can chose which value and suit to assign each card- but you will have to remember each one, so pick something easy such as a pattern of odd and even numbers, or the CHaSeD order.
E.g.
1Clubs, 3Clubs, 5Clubs, 7Clubs,
2Hearts, 4Hearts, 6Hearts, 8Hearts,
1Spades, 3Diamonds, 5Diamonds, 7Spades,
2Spades, 4Diamonds, 6Spades, 8Diamonds.

If memorisation is not a problem for you, you could use multiple packs of cards to make the same sequence again and again. This way, you can stack each sequence and have a deck of not just 16 cards but 32, 48, or even 64.

So long as you know who is holding the red card, you will always be able to deduce the rest of the cards, as each positioning of red cards has distinct values and suits attached. For the above example:

Say that the 2nd and 4th participants have red cards: the sequence for the 4 participants must be BRBR. The only substring of cards in which this order of red and black cards occurs is the last 4 cards:
2Spades, 4Diamonds, 6Spades, 8Diamonds.

Therefore, I know that the 4 participants must have these exact cards.

SIDE NOTE: When we reverse the sequence (BBRR), which obtains the same results, we call this the negation.

The number of distinct de Bruijn sequences B(k, n) is calculated with:

(k!)^(k^(n−1)) / k^n