Session notes
Chapter 2 of Magical Mathematics closes here with the mathematics behind the 32-card colour-pattern effect. De Bruijn sequences carry through chapters 3 and 4, where the same principle – local information determines global structure – extends to two-dimensional arrays; later chapters turn to other shuffles, the Gilbreath principle, and perfect shuffles.
3:09 No new tricks today. The effect: a rigged 32-card deck, cut freely, top five dealt. Holders of red cards stand, and the five-bit colour pattern is all that is needed.
5:18 The book’s coding: 0 black, 1 red. The first bit gives colour; the second pins the suit: 00 clubs, 01 spades, 10 diamonds, 11 hearts. Mnemonics help – 00 looks like two club lobes, 10 squashed suggests a D for diamond, 11 is “One Love” for hearts. The last three bits give the card number in binary, with 000 read as 8.
8:01 Ravi asked whether a cut disturbs the order the trick relies on. A cut is a rotation of a cyclic sequence: relative cyclic order is preserved, and wraparounds are part of the interpretation. Sunita noted the suit coding is simply lexicographic, matching alphabetical order.
11:34 Rather than taking the sequence from the book, we asked what property any working sequence must have. Five bits distinguish values, so 32 cards is the maximum. I claimed equal numbers of black and red cards are required, then admitted that is less obvious than I made it sound.
14:42 Any number of cuts reduces to one cut, which we cannot control. Write the 32-card colour pattern as a bit string and form the 32 cyclic reads of length 5. Cutting nine cards from the book’s sequence gives 01100; cutting ten gives 11001.
17:42 The answer from the chat: every 5-bit string must appear exactly once. A repeated read at two positions means two distinct cards share a prediction, so one performance fails. The constraint is exact: 32 positions, 32 distinct strings, no slack.
21:02 These are de Bruijn sequences. A de Bruijn sequence of order has length and contains every -bit string exactly once as a cyclic substring. The count, attributed to de Bruijn in the book, is .
22:03 A greedy construction: keep writing 0 until a fifth 0 would repeat 00000, then write 1, and so on. Whether greedy always succeeds or sometimes requires backtracking was left as food for thought.
24:12 The book’s mnemonic (page 26): from five bits , the next bit is , a linear shift register rule. Starting from 00001 and iterating produces the book’s 32-bit sequence. The book states this without proving the result is a de Bruijn sequence. As a performance tip, it replaces memorising the sequence: compute the sixth bit from the first and third, read off the next card, repeat.
26:18 Vinod asked whether the rule works for every de Bruijn sequence. No: the rule forces the whole sequence from any starting point, so it can hold for at most one sequence up to cyclic shift. Sunita noted that starting from 00000 will not work; the book starts from 00001.
30:32 The main construction gives a constructive existence proof for every via Euler tours. Vertices are all bit strings of length , giving vertices. There is a directed edge from to when the -bit suffix of equals the -bit prefix of . (A typo on my slide had where it should be .)
33:42 Every vertex has exactly two out-neighbours: the first bits of any out-neighbour are forced, only the last bit is free. In-degree is two by symmetry (Pratik said two, Ravi said one); and carry self-loops, each counting once toward in-degree and once toward out-degree. Total edges: , exactly the length we want.
38:04 The case: vertices 00, 01, 10, 11, overlap of one bit. 00 to 01 is an edge; 00 to 11 is not. Self-loops at 00 and 11.
40:13 A directed graph admits a closed Euler tour if and only if in-degree equals out-degree at every vertex – a well-known fact we did not prove. Our graph is 2-regular, so a tour exists, and polynomial-time algorithms find one.
42:24 To generate the sequence: walk the Euler tour and after each edge write the last bit of the vertex arrived at. edges yield bits. We worked through the graph from vertex 00, handling the double edge between 01 and 10 and both self-loops.
46:40 Pratik suggested that greedy feels like taking an Euler tour, so it should work without backtracking. Plausible, though my ad hoc attempts needed corrections; the connection deserves a precise argument.
48:51 Ravi noted that different Euler tours give different de Bruijn sequences, suggesting that counting sequences amounts to counting Euler tours in this graph. Sunita: for , starting from 001 with gives the sequence. So there are linear rules for and ; is there a general pattern?
50:53 The construction works because any target -bit string splits into a -bit prefix vertex and a -bit suffix vertex, overlapping in bits and joined by an edge. When the tour traverses that edge, the preceding bits printed spell the first vertex (an induction, with wraparound handled cyclically) and the new bit completes the target. The book labels each edge with the -bit string it produces.
1:00:27 The closed form appears in the book without proof. Ravi: reading the 32 cyclic reads as binary numbers gives every integer from 0 to , with 0 standing in for in the trick. A conjecture from the chat: for odd , the linear rule is plus a bit one position further along as grows ( for , for ); even orders remain unexplored.
1:02:26 Up next: two-dimensional de Bruijn arrays.
To think about
- Make the greedy algorithm precise and prove it needs no backtracking, or find a case where it does.
- Prove that starting from 00001 with produces a de Bruijn sequence of order 5.
- Prove the Euler-tour criterion for directed graphs (in-degree equals out-degree at every vertex is sufficient as well as necessary for a closed tour).
- Show that every de Bruijn sequence of order arises from an Euler tour in the graph on -bit strings.
- Find linear bit-generation rules for other orders, including even ones.