🔸 A deck with 32 cards is handed out to the audience. 🔸 They cut the deck any number of times. 🔸 Then someone picks the top card, passes the deck: repeat 4X - a total of five cards are picked. 🔸 Those who got red cards are asked to stand up. 🔸 All cards are identified. /2

Interpreting red = 1 & black = 0, any sequence of five cards signals a bit string of length 5. This is, at least in principle, enough to ID one of the cards in a 32-card deck, for sure. Although the principle to practice journey is not trivial. 👀 Plus, we ID all 5 cards! /3

The deck, of course, is setup: the cards appear in a specific order, one whose relevant properties are unperturbed by cut shuffles. Note that we have no control over how many times the deck is cut, so the top card could be effectively anywhere in from the original sequence. /4

So what we need is a sequence S of 32 bits where every 5-length bit string appears exactly once*. POA: 🔸 make a dictionary D that maps 5-length bitstrings to distinct cards (strings starting w/0 to black cards and strings starting w/1 to red) 🔸 memorize S,D 🔸 profit /5

*exactly once as a substring; and we also include wraparounds, which is to say (for example) that the 5-length substring starting at position 31 picks up the last two bits and the first three. /6

How do we produce such a string? Do they even exist? Turns out such sequences go by de Bruijn sequences: they do in fact exist, even in abundance, and there are several ways of finding them. /7

Here I'll describe one way that involves walking along an Euler tour in a specific graph. But if you are just interested in the trick, then here's a couple of quick things first. /8

Memorizing S and D sounds like rather a lot. Here's an easy way out for the dictionary bit: use the first two bits to code for the suit and the last three to code for the value (map 000 to 8). /9

Now you could memorize all of S: - but it turns out that this particular sequence has a really nice property that serves as a useful mnemonic. /10

If you are anywhere in the sequence, to get the next bit, hop back two bits and make note of it (a) and hop back two bits more and make note of that too (b). The subsequent bit is always* (a+b) mod 2. /11

*There is one important exception to this, which can be avoided by dropping the first bit and working with a deck of 31 cards; or by committing the exception at around the 4th/5th bits to memory. /12

So if you have your deck setup right, and all the cut shuffles are carried out without too much enthusiasm, and the audience faithfully reports the colors of the cards, you are now pretty much all set to identify all of them. /13

But now let's get back to something something graphs something something. Remember we wanted a method to construct de Bruijn sequences? /14

Here is a graph for your consideration: 🔸 vertices: all bit strings of length four. 🔸 edge from u to v if the three-bit suffix of u matches exactly the three-bit prefix of v. /15

Not hard to see: ☑ indegree = outdegree = 2 for all vertices ☑ number of vertices = 16 ☑ number of edges = 32 ☑ number of self-loops = 2 (at 0000 and 1111) /16

I've drawn it up, if you want to take a look: (Ok, just to be clear: I just wrote up the edges, an engine did the drawing.) /17

So, take a walk in this graph, go on. When you go from u to v, there's only one new bit to see. The last three bits of u and first three bits of v are the same, so just make a note of the last bit of v. /18

Every edge traversed gives you a new bit. Punchline: the full Euler tour gives you a de Bruijn sequence of length 32. /19

This is not hard to see: suppose you want to spot the bitstring PQRST in your sequence. Well, at some point in our walk on the graph, we moved from the vertex representing PQRS to the one representing QRST. /20

Indeed, this must have happened at some point, since we visit every edge exactly once. This made us add T to whatever sequence we had so far. Let's rewind our walk a bit and see what happened in the last few steps too: LMNO → MNOP → NOPQ → OPQR → PQRS → QRST /21

These steps must have triggered the bits PQRST to be output, exactly as desired. (If you hit a wall while rewinding, it's a tour, just keep going further back from the starting point. The bitstring you're looking for in this case manifests as a wraparound.) /22

So there! An Euler tour that gives you a de Bruijn sequence that drives a nice card trick. This hopefully motivates algorithms for finding Euler tours! That's a story for another day. /23

This and several other amazing tricks + math + both magical and mathematical anecdotes appear in the excellent book: Magical Mathematics: The Mathematical Ideas That Animate Great Magic Tricks Thanks to @ccl_iitgn for showing me this book and a lot of magic too! /24

PPS. Notes corresponding to this thread should be up soon. Why yes, I am indeed procrastinating, thanks for asking. 😬 /26