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:
And here’s its output:
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
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
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
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.