Magical mathematics: The mathematical ideas that animate great magic tricks.
Authors: Persi Diaconis and Ron Graham
Published 2012 by Princeton University Press
According to Diaconis and Graham (2012), de Bruijn sequences are at the heart of several wonderful card tricks. Being unable to recall if I had come across these sequences I was glad the intention of the authors,(one a mathematician and juggler and the other a mathematician and magician), was to explain the mathematics. Nicolaas Govert de Bruijn (1918-2012) was a Dutch mathematician.
In brief the card trick involves members of the audience removing a card from the pack. The card holders indicate if their card is red (R) by standing. The performer then names the card held by each person standing. The authors explain that if the pack used has only eight cards and three audience members removed a card, there are eight possible results:
RRR RRB RBR RBB BRR BRB BBR BBB
From this, the performer has sufficient information to identify who has which card! Read the book to see exactly how. The sequence RRRBBBRB is sufficient to specify the eight possibilities.
To explain, "a de Bruijn sequence with window length k is a zero/one sequence of length [2.sup.k] ... such that every k consecutive digits appears just once (going around the corner)" (p. 19).
For our cards if we replace R and B with 1 and 0 we have the equivalent sequence 11100010. As in the example, if three cards are selected, we need a window of length 3. Figure 1 shows all eight possibilities and clarifies what is meant by 'going around the corner'. Hence, de Bruijn sequences are cyclic sequences.
Diaconis and Graham explain that with a de Bruijn sequence of window length k, they can perform their trick with [2.sup.k] cards. Thus they perform the trick with five people and 32 cards.
Focusing on the mathematics, the authors discuss the question "Are there de Bruijn sequences for every k?" and show how graph theory can be used to answer this. Graph theory including directed graphs, Eulerian cycles, and Hamiltonian paths are typical content in upper secondary general or further mathematics subjects.
For k = 3, there are four zero/one strings of length k - 1, namely 00, 01, 10, 11 or simply represented by the de Bruijn sequence, k = 2, n = 2 where n represents the number of elements, here zero or one, is 0011. Begin your graph with these four possibilities as the vertices. Complete the graph by adding "an edge going from vertex x to vertex y if there is a zero/one string of that length k that has x at its left and y at its right". Figure 2 (p. 20) shows the results. Needless to say, that for larger k, they get harder to draw. An Eulerian circuit will produce the de Bruijn cycle.
Did you know that de Bruijn arrays are used by digital pens? What is the link between DNA, codes, de Bruijn sequences and Sanskrit prosody? How is the game Rock, paper, scissors related to magic tricks? How and why are binary numbers used to describe cards? What is the mathematics behind shuffling cards and do the cards end up in random positions or not? What is the connection between the Gilbreath principles of card shuffling and Mandelbrot set? de Bruijn wrote about card shuffling and related the Gilbreath principle to Penrose tiles. This book links so many interesting parts of mathematics together, often unexpectedly. In addition, all of the mathematics is related to card tricks or juggling or other magic. No review of this book can do it justice--you need to read it.
Note the book is available for purchase in Australia from Footprint Books.
Australian Catholic University