You're reading: cp's mathem-o-blog, Videos

David’s de Bruijn sequence card trick

A few days ago, my friend David asked me if I could help him with a card trick. I said I could, hence this post. I managed to pin David down in front of my camera long enough for him to demonstrate the trick; a full explanation follows this video:

The basic trick is pretty well-known: Card Colm wrote about it for his MAA column a few years ago, and collected a pretty extensive list of people who have written on the subject. David came across it through Persi Diaconis and Ron Graham’s book Magical Mathematics, but hadn’t read the book in detail before we tried to work the trick out for ourselves.

A de Bruijn sequence of length $k$ on an alphabet $A$ is a cyclic sequence which contains all possible strings of length $k$ exactly once. It follows that if you are given a string of $k$ letters, you can tell exactly where it occurs in the sequence. Since it doesn’t matter what the symbols in the alphabet $A$ are as long as they’re all different, we can just refer to a de Bruijn sequence $(k,n)$, containing all subsequences of length $k$ using the numbers $\{0,\dots,n-1\}$.

We decided we were going to assign each card in a standard deck a 6-digit binary string (because $2^6 = 64 \gt 52$) and to arrange them in the order of a $(6,2)$ de Bruijn sequence. Then, if we asked someone to cut the deck, draw out six cards and tell us their colours, we could work out exactly which cards they had in their hand.

There can be more than one de Bruijn sequence for each choice of $k$ and $n$, so we could pick the one that was easiest to construct. For binary sequences, this rule always generates a de Bruijn sequence of length $k$: write $k-1$ zeroes followed by a $1$, then subsequent letters are given by $x_{i+6} := x_i+x_{i+1} \pmod 2$ — add two adjacent numbers to get the one six places along. Because addition modulo $2$ is the same thing as subtraction modulo $2$, the same trick works backwards: $x_i = x_{i+1} + x_{i+6}$.

So the only thing left to do was to assign binary strings to cards. I decided that four digits for face value and two for suit would do, since it lets you split the calculation up into two small steps. So the face values go from $0 = A$, to $12 = K$, and the suits go Diamonds, Clubs, Hearts, Spades. In a hand of six cards drawn from the deck, the sequence of red or black colours gives the value of the last card drawn.

The only problem is that there are twelve strings representing face values greater than $12$, and I don’t think it’s possible to construct a de Bruijn sequence where they all occur in one block. But equally, because there are $64$ six-digit binary strings, any sequence we used would have twelve unused strings at the end. So we had to make one kludge and manually swap “bad” strings in the usable part of the sequence with “good” ones at the end.

Now, decoding binary strings is pretty tedious work, and finding these unusable strings is especially so, so I quickly wrote a Python script to do the calculations for me. Here it is:

# de Bruijn card trick computatorator
# by Christian Perfect
# based on a trick by Persi Diaconis and Ron Graham

#names of cards
faces = ['King','Ace','2','3','4','5','6','7','8','9','10','Jack','Queen']
suits = ['Diamonds','Clubs','Hearts','Spades']

#generate de bruijn sequence
sequence = [0,0,0,0,0,1]
for i in range(6,64):
	sequence.append( (sequence[i-6]+sequence[i-5]) % 2 )

#get a string of binary digits representing an integer
def binarise(n,length):
	digits=[]
	while n>0:
		digits.insert(0,int(n%2))
		n=(n-n%2)/2
	digits = [0]*(length-len(digits))+digits	#pad to the desired length
	return digits

#decode a string of binary digits to an integer
def debinarise(digits):
	n=0
	for i in digits:
		n*=2
		n+=i
	return n

#decode a six-digit binary string to a card
def decode_sequence(seq):
	number = debinarise(seq[:4])
	suit = debinarise(seq[4:])
	return number,suit

#turn a card into a six-digit binary string
def encode_card(card):
	number,suit = card
	return ''.join([str(x) for x in binarise(number,4)+binarise(suit,2)])

#display a card's binary encoding and its name
def show_card(card):
	number,suit = card
	return '%s: %s of %s' % (encode_card(card), faces[number], suits[suit])


# The actual computation!
sequence*=2	#take two copies of the sequence to cope with the cycle at the end

# Get the ordering of the (64, not all real) cards from the sequence
cards = [decode_sequence(sequence[i:i+6]) for i in range(0,64)]

# The deck of cards consists of the first 52
deck = cards[:52]

# Get the unused cards from the end of the 64-deck which have usable values
castoffs = [(x,y) for (x,y) in cards[52:] if x<13]
# Separate them into red and black
castoffs_red = [(x,y) for (x,y) in castoffs if y%2==0]
castoffs_black = [(x,y) for (x,y) in castoffs if y%2==1]

# Get the cards from the 52-deck that don't have usable values
toswap = [(x,y) for (x,y) in deck if x>=13]
swaps = {}

# Match up bad cards in the 52-deck with good cards in the castoffs
for card in toswap:
	number,suit = card
	b=castoffs_red.pop() if suit%2==0 else castoffs_black.pop()
	swaps[card]=b

# Show the resulting ordering of the real 52-card deck
for i in range(0,52):
	digits = sequence[i:i+6]
	card = decode_sequence(digits)
	if card in swaps.keys():
		card = swaps[card]
	print(show_card(card))

# Show which bad codes are swapped with which good ones
print('Swaps')
for a,b in swaps.items():
	print('%s -> %s' % (encode_card(a),show_card(b)))

And here’s its output:

000001: Ace of Clubs
000010: Ace of Hearts
000100: 2 of Diamonds
001000: 3 of Diamonds
010000: 5 of Diamonds
100001: 9 of Clubs
000011: Ace of Spades
000110: 2 of Hearts
001100: 4 of Diamonds
011000: 7 of Diamonds
110001: King of Clubs
100010: 9 of Hearts
000101: 2 of Clubs
001010: 3 of Hearts
010100: 6 of Diamonds
101001: Jack of Clubs
010011: 5 of Spades
100111: 10 of Spades
001111: 4 of Spades
011110: 8 of Hearts
011111: 8 of Spades
000000: Ace of Diamonds
100000: 9 of Diamonds
101000: Jack of Diamonds
010001: 5 of Clubs
100011: 9 of Spades
000111: 2 of Spades
001110: 4 of Hearts
011100: 8 of Diamonds
101111: Queen of Spades
110010: King of Hearts
100100: 10 of Diamonds
001001: 3 of Clubs
010010: 5 of Hearts
100101: 10 of Clubs
001011: 3 of Spades
010110: 6 of Hearts
101101: Queen of Clubs
011011: 7 of Spades
010111: 6 of Spades
101110: Queen of Hearts
011101: 8 of Clubs
101011: Jack of Spades
110000: King of Diamonds
101100: Queen of Diamonds
011001: 7 of Clubs
110011: King of Spades
100110: 10 of Hearts
001101: 4 of Clubs
011010: 7 of Hearts
010101: 6 of Clubs
101010: Jack of Hearts
Swaps
110101 -> 010101
110110 -> 110000
110111 -> 010111
111101 -> 011111
111001 -> 101111
111011 -> 101011
111010 -> 000000
110100 -> 100000

The Python script constructs the de Bruijn sequence, decodes it into a sequence of 64 cards (some of them virtual), finds bad cards in the deck of 52 and swaps them with good cards in the pile of twelve “castoffs” at the end, making sure the colour is preserved. It turns out there are eight bad cards in the deck that need swapping.

So, we only need to remember eight pairs of binary strings and a simple iterative rule which constructs the sequence in order to perform the trick. Not bad for an afternoon’s work!

References

Universal cycles for combinatorial structures by Chung, Diaconis and Graham

Products of Universal Cycles by Diaconis and Graham

Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks by Diaconis and Graham

What’s Black and Red and Red All Over? by Colm Mulcahy

13 Responses to “David’s de Bruijn sequence card trick”

  1. Ian Thomson

    Christian and David

    I shudder to think what “koala fan” might mean.

    However, I’m writing to thank you both for this webpage and its resources. I’m a performing magician, and this is a brilliant method for performing what could be an amazing effect. Something similar is described in Alex Stone’s “Fooling Houdini”, but the exact details are left out and from its description I doubt it’s as clean as the script you’ve put together here.
    .
    However, I doubt that many magicians would be able to follow the theory (unless they’ve learned binary arithmetic and sequence theory in one of their many holidays at Her Mayesty’s Pleasure). As well as being a magic-nerd I’m an ex-scientist, and am in IT, so I managed to grasp most of it with a little effort. But for me this is an advantage, as I can’t imagine any of my magic-nerd brothers wanting to perform it.

    Anyway. Can I point out that, in performance (if you’re worried about that) you don’t need to ask for the colour of each card? Just the pattern of one colour would do. Plus if you could discern the colour spread of the six cards without asking any questions at all (invisible markings on the back, for example), that would be a miracle indeed. I’m working on the latter idea.

    And that’s it. Thank you again for the work, ingenuity, mental abilities and skill behind putting this together. A 52-card De Bruijn beats all the other ideas I’ve seen for cleanliness, including Colm’s.

    Cheers

    Ian

    Reply
  2. Rob Stanley

    Thanks for the code. I’ve modified it slightly to better suit my needs, and because I think you can take a few more shortcuts.

    1. I’ve swapped the order to suit then face value.
    2. A face value of 1 is the Ace, 2 the 2, and so on.
    3. I’ve included 2x Jokers (counted as black).
    4. I’ve rotated the sequence slightly.

    This gives me an ordering for the deck of 52 cards of which 6 are in the castoffs. But the replacement rules (only 4, and done by hand!) are easier (also why I need the Jokers in the deck).

    1. Impossible Clubs are face value – 13.
    2. Impossible Spades are Jokers.
    3. The ’14 of Diamonds’ is the 8 of Diamonds.
    4. The ’15 of Diamonds’ is the Queen of Diamonds.


    #names of cards
    faces = ['Ace','2','3','4','5','6','7','8','9','10','Jack','Queen','King']
    N_faces = faces.__len__()
    suits = ['Clubs','Spades','Diamonds','Hearts']

    #generate de bruijn sequence
    def debruijn():
    sequence = [0,0,0,0,0,1]
    for i in range(6,64):
    sequence.append( (sequence[i-6]+sequence[i-5]) % 2 )
    return sequence

    #get a string of binary digits representing an integer
    def binarise(n,length):
    return bin(n)[2:].zfill(length)

    def debinarise(digits):
    binary = ''.join([str(x) for x in digits])
    return int(binary,2)

    #decode a six-digit binary string to a card
    def decode_sequence(seq):
    number = debinarise(seq[2:])
    suit = debinarise(seq[:2])
    return suit,number

    #turn a card into a six-digit binary string
    def encode_card(card):
    suit,number = card
    return ''.join([str(x) for x in binarise(suit,2)+binarise(number,4)])

    #display a card's binary encoding and its name
    def show_card(card):
    suit,number = card
    if (suit==1 and (number == 0 or number > 13)): #unknown spades
    name = "Joker"
    elif (suit==0 and number > 13):
    name = "%s of %s" % (faces[number-14], suits[suit])
    elif (suit==2 and number == 14):
    name = "%s of %s" % (faces[7], suits[3])
    elif (suit==2 and number == 15):
    name = "%s of %s" % (faces[11], suits[3])
    else:
    name = "%s of %s" % (faces[number-1], suits[suit])
    return '%s: %s' % (encode_card(card), name)

    def show_cards(cards):
    for card in cards:
    print(show_card(card))

    def rotate(l,n):
    return l[n:] + l[:n]

    sequence = rotate(debruijn(),2)
    sequence*=2
    cards = [decode_sequence(sequence[i:i+6]) for i in range(0,64)]

    # The deck of cards consists of the first 52
    deck = cards[:54]

    # Get the unused cards from the end of the 64-deck which have usable values
    castoffs = [(x,y) for (x,y) in cards[54:] if y=N_faces+1 or y == 0]

    toswap.sort()
    castoffs.sort()

    print "Cards:"
    for i in range(0,54):
    digits = sequence[i:i+6]
    card = decode_sequence(digits)
    print(show_card(card))

    print "\nCastoffs:"
    show_cards(castoffs)

    print "\nTo remember:"
    print "1. Impossible Clubs are face value - 13."
    print "2. Impossible Spades are Jokers."
    print "3. The '14 of Diamonds' is the 8 of Diamonds."
    print "4. The '15 of Diamonds' is the Queen of Diamonds."
    show_cards(toswap)


    Cards:
    000100: 4 of Clubs
    001000: 8 of Clubs
    010000: Joker
    100001: Ace of Diamonds
    000011: 3 of Clubs
    000110: 6 of Clubs
    001100: Queen of Clubs
    011000: 8 of Spades
    110001: Ace of Hearts
    100010: 2 of Diamonds
    000101: 5 of Clubs
    001010: 10 of Clubs
    010100: 4 of Spades
    101001: 9 of Diamonds
    010011: 3 of Spades
    100111: 7 of Diamonds
    001111: 2 of Clubs
    011110: Joker
    111101: King of Hearts
    111010: 10 of Hearts
    110100: 4 of Hearts
    101000: 8 of Diamonds
    010001: Ace of Spades
    100011: 3 of Diamonds
    000111: 7 of Clubs
    001110: Ace of Clubs
    011100: Queen of Spades
    111001: 9 of Hearts
    110010: 2 of Hearts
    100100: 4 of Diamonds
    001001: 9 of Clubs
    010010: 2 of Spades
    100101: 5 of Diamonds
    001011: Jack of Clubs
    010110: 6 of Spades
    101101: King of Diamonds
    011011: Jack of Spades
    110111: 7 of Hearts
    101110: 8 of Hearts
    011101: King of Spades
    111011: Jack of Hearts
    110110: 6 of Hearts
    101100: Queen of Diamonds
    011001: 9 of Spades
    110011: 3 of Hearts
    100110: 6 of Diamonds
    001101: King of Clubs
    011010: 10 of Spades
    110101: 5 of Hearts
    101010: 10 of Diamonds
    010101: 5 of Spades
    101011: Jack of Diamonds
    010111: 7 of Spades
    101111: Queen of Hearts

    Castoffs:
    000001: Ace of Clubs
    000010: 2 of Clubs
    111000: 8 of Hearts
    111100: Queen of Hearts

    To remember:
    1. Impossible Clubs are face value - 13.
    2. Impossible Spades are Jokers.
    3. The '14 of Diamonds' is the 8 of Diamonds.
    4. The '15 of Diamonds' is the Queen of Diamonds.
    001110: Ace of Clubs
    001111: 2 of Clubs
    010000: Joker
    011110: Joker
    101110: 8 of Hearts
    101111: Queen of Hearts

    Reply
  3. Rob Stanley

    Sorry! Above that should read:
    3. The ’14 of Diamonds’ is the 8 of Hearts.
    4. The ’15 of Diamonds’ is the Queen of Hearts.

    Reply
    • Andrew Brimmell

      I can’t seem to make this version work. The sequence works, but it doesn’t seem to follow the red and black sequence of the cards. Am I missing something?

      Reply
      • Rob Stanley

        Perhaps you missed my changes?
        1. I’ve swapped the order to suit then face value. So the first two bits are suit, and the remaining bits are the face value.
        2. A face value of 1 is the Ace, 2 the 2, and so on. Rather than counting from 1 as in the original code.

        Reply
  4. H

    This is really cool. I’ve just got one question: I’m trying to work out if the cyclical nature of the De Bruijn sequence is disrupted/broken by shortening it so that 52 cards can be used. If you cut the deck, complete the cut, and then cut again, will this still work? I think the next card in the sequence, after the 101010 (Jack of Hearts), is either 110101 (14 of clubs) or 010101 (6 of clubs) depending on whether the swap rule is used, but the cycle card is the Ace of clubs. Or have i missed something (probably really obvious!)?

    Thanks for sharing, it’s great!

    Reply
  5. n.gururajan

    excellent application of binary system.
    give me some more.
    thank you
    with best wishes
    n.gururajan

    Reply
  6. JL

    The order of 52 cards listed by Christian does not appear to always work when the sequence wraps around. I’ll try to show an example below since I may be missing something and hopefully someone can correct me, but first just to keep things straight, here is a summary of how I believe things are defined:

    4 MSBs of the binary sequence when decoded to a decimal number represents the value of the card according to this rule:
    4 MSBs + 1 = value of the card (ignoring suits)
    where 1= Ace, 2 = Two, … 11 = Jack, 12 = Queen, 13 = King.

    For example:
    000001: Ace of Clubs -> 0 + 1 = Ace
    100001: 9 of Clubs -> 8 + 1 = Nine

    In the above, the 2 LSBs represent the suit as follows:
    00 = 0 = Diamonds
    01 =1 = Clubs
    10 = 2 = Hearts
    11 = 3 Spades

    When looking at sequences cards:
    0 = red
    1 = black

    This sequence works for the 6 cards dealt out after a cut and note this does not involve the sequence wrapping around (i.e. wrap occurs when considering the last card which is the Jack of Hearts and then the first card which is the Ace of Clubs):
    100001
    Decodes to: 9 of Clubs

    This corresponds to the 9 of clubs being the last card and this means the 6 cards for this sequence are the first 6 cards in Christian’s list:
    Ace of Clubs
    Ace of Hearts
    2 of Diamonds
    3 of Diamonds
    5 of Diamonds
    9 of Clubs

    However, this sequence after a cut starting with the 6 of Clubs does not work and this does involve the sequence wrapping around since the Jack of Hearts and the Ace of Clubs are involved (i.e. the first and last cards of the list):
    101000
    Decodes to: Jack of Diamonds

    These are the 6 cards for this sequence and notice how the last card below is the 3 of Diamonds and not the Jack of Diamonds that would be expected:
    6 of Clubs
    Jack of Hearts (last card in the list)
    Ace of Clubs (1st card in the list)
    Ace of Hearts
    2 of Diamonds
    3 of Diamonds

    Please let me know if you see anything that I’m missing. BTW, maybe this is what ‘H’ was asking about but I wasn’t sure.

    Thanks!

    Reply
    • Christian Perfect

      You’re right – it doesn’t wrap around, because we’re missing 12 imaginary cards.We thought that was a reasonable compromise in return for being able to do the trick with a full standard deck.

      Reply
      • JL

        OK, thanks for confirming.

        In Alex Stone’s book “Fooling Houdini”, he described the trick with 52 cards and there were no restrictions regarding the wrap around. Apparently there is a sequence that does work with 52 cards but without the nice encoding that you have incorporated? Alex does mention that the order of the 52 cards needs to be memorized and gives tips for this memorization task.

        With your compromised approach, the deck needs to be cut such it is no closer than 6 cards from the end, but thanks to your encoding I think it is still a very powerful trick!

        One way to handle the cut card restriction could be to ask someone to cut the deck. If they cut it very thin at the end (possibly within the last 5 cards) then you could simply ‘burn’ 6 cards before displaying the 6 cards that will be used for the trick. There are probably better ways to handle this situation where the cut is within the last 5 cards…

        Thanks again.

        Reply
        • Jean-Marie Beckers

          Hi,
          I’m also experimenting with the idea (bot not using the color information but suit information needing less cards to be taken by spectators and reduces also the cycling problem). Concerning the cycling problem: why not just take thin cards and add 12 duplicates to close the loop and use a simple rule such as face value to read by subtracting 13 whenever the value is too large. ?

          Reply

Leave a Reply

  • (will not be published)

$\LaTeX$: You can use LaTeX in your comments. e.g. $ e^{\pi i} $ for inline maths; \[ e^{\pi i} \] for display-mode (on its own line) maths.

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>