Magical Mathematics

This post documents a few magic tricks based on mathematics that I found rather amusing. We follow the book of the same name by Diaconis and Graham, as well as this MO post. You may enjoy working out how these are performed, and solutions can be found in the aforementioned sources, so I'll leave them here as a list.

• (Gergonne) Suppose I have 21 playing cards. I distribute them in 3 columns and tell you to choose mentally a card. Then just indicate in which column the card is. I pick up one of the columns which doesn't contain your card, then the column which contains your card then the remaining column. Now I deal the cards in 3 columns again, starting from the left to the right, and repeating the process until there are no cards left in my hand. I ask you to indicate to me in which column your card is. I repeat step 2 then 3. I repeat step 2. Now by counting either way in the deck of 21 cards, your card will be the 11th card.
• A magician asks Alice to choose two integers between 1 and 50 and add them. Then add the largest two of the three integers at hand. Then add the largest two again. Repeat this around ten times. Alice tells the magician her final number $n$. The magician then tells Alice the next number. 
• A rope is attached to the two upper corners of a rectangular picture (each end of the rope to one corner). How can I hang this picture on a wall, using two nails, so that if you remove one nail (any of the two) the picture will fall? Same question with any given number of nails. 
• A volunteer is given a deck of 52 playing cards and asked to pick five of them. They show the cards to the magician's assistant. The volunteer can then choose which 4 cards get passed to the magician. The assistant passes these to the magician, who promptly names the 5th card. How?
• An ordinary deck of fifty-two cards is handed out as above. Three spectators are enlisted, the deck is cut by each, and three consecutive cards are removed, one per spectator. The performer says to the first spectator, “As a warm-up, I want to try an easy test with you. Tell me the value of your card, but not the suit. It’s only one out of four possibilities, but we hardly know each other.” Say the spectator answers, “I have an eight.” The performer answers, “Hold on. I want to work with all three of you at once, like a chess expert.” To the second spectator, “Tell me the suit of your card only, not the value. That’s a one-in-thirteen problem.” Say the spectator answers, “I have a heart.” To the third spectator, “I’ll save the hardest for last. I don’t want you to tell me anything, just concentrate on your card.” Continuing, the performer says, “Spectator one, you chose an eight. Try not to react, it could have been any of the four eights—clubs, hearts, spades, or diamonds; you shifted a little when I said ‘clubs.’ I think you have the eight of clubs.” The spectator holds the card up to show that the performer is correct. To the second spectator, “I know you have a heart (if you’ll pardon the expression!), but which one? High, medium, low? Face card or spot? Even or odd? Aha, I see; it is the king of hearts.” The spectator holds up the card to show the guess is correct. Finally, after similar banter, the performer correctly names the third spectator’s card without asking a single further question—“It is the three of spades.”

One trick I would like to spoil discuss is the following: 

The performer has a deck of cards in its case (a few rubber bands around the deck will help ensure no disaster happens). The deck is tossed to an audience member who tosses it to another, and so on, until the deck is far at the back of the room.  To actually perform this trick, you need at least five people in the audience but it is effective with an audience of a thousand. The final deck holder is asked to remove cards from the case, drop the case on the floor, and then give the deck a straight cut at a random position. The deck is passed to a second spectator who is asked to cut and pass 

it on. Finally, when a fifth spectator cuts, ask that the top card be taken off. The deck is then passed back to the fourth spectator who removes the current top card. Each of the five spectators in turn removes a card. The performer now asks, “This may sound strange but would each of you please look at your card, make a mental picture, and try to send it to me telepathically?” As this is done the performer concentrates and appears confused: “You’re doing a great job, but there is too much information coming in for me to make sense of. Would all of you who have a red card please stand up and concentrate?” Suppose that the first and third spectators stand. The performer appears relieved and says, “That’s perfect. I see a seven of hearts?” (One of the spectators shows that this is indeed the thought- of card.) “And a jack of diamonds? Yes.” Now, focusing on the other three spectators, the performer names all three black cards.There is nothing left out of the above description; the cards are well 

out of the performer’s control and aren’t tricked or marked in any way. So how does it work?

I will simply describe the mathematics that goes on behind the scenes and leave it to the reader to figure out/read in the sources how to turn this into a convincing trick.

A de Bruijn sequence with window length \( k \) is a zero/one sequence of length \( 2^k \) (this is just \( 2 \times 2 \times \cdots \times 2 \), \( k \) times) such that every \( k \) consecutive digits appears just once (going around the corner). Thus, 11100010 is a de Bruijn sequence of window length 3. In particular, knowing the first $k$ digits of a de Bruijn sequence is sufficient to determine the entire sequence. We now describe an ingenious method of construction.

Form a graph with vertices being the strings of zero/one symbols of length \( k - 1 \) (so there are \( 2^{k-1} \) of them), and an edge going from vertex \( x \) to vertex \( y \) if there is a zero/one string of length \( k \) that has \( x \) at its left and \( y \) at its right. This graph has an Eulerian circuit if and only if each vertex has an equal number of edges leading in as leading out. For the de Bruijn graph, there are exactly two edges leading out of each vertex — a zero/one \( (k - 1) \)-tuple can be finished off to a \( k \)-tuple in just two ways: add 0 or add 1. Similarly, there are exactly two ways of coming into a vertex.

Furthermore, it is not hard to check (by changing one digit at a time) that we can go from any vertex to any other vertex along some path following the arrows. Since we have verified the conditions for Euler’s theorem, we may use its conclusion: de Bruijn sequences exist for every \( k \).

The proof of the theorem even gives an algorithm of sorts for construction: Start at any vertex (say \( k - 1 \) zeros), choose any available arrow leading out, erase this arrow, and continue. The proof shows you can cover each edge just once without getting stuck. What’s more, the construction forces a cycle; the last step winds up at the original start.

The number of de Bruijn sequences is a consequence of the following theorem, whose name derives from the surnames of the people who proved it:

BEST theorem: Given a connected, directed, and finite Eulerian graph \( G = (V, E) \), let  \( t_s(G) \) is the number of spanning arborescences of \( G \) rooted at vertex \( s \), i.e. trees directed towards the root at a fixed vertex $w$ in $G$, and \( \deg(v) \) is the out-degree (or in-degree) of vertex \( v \). Then the number of Eulerian tours around the graph is

\[\operatorname{et}(G) = t_s(G) \cdot \prod_{v \in V} (\deg(v) - 1)!,\]

The factor $t_s(G)$ can be computed using Kirchoff's matrix-tree theorem.

Proof: We will prove the following: the number of Eulerian tours starting from \( s \) is

\[\operatorname{et}_s(G) = t_s(G) \cdot \deg(s)! \cdot \prod_{v \in V \setminus \{s\}} \frac{1}{(\deg(v) - 1)!}.\]

This is equivalent since choosing a tour starting at $s$ is equivalent to picking a starting out-edge, so we scale up by a factor of $\deg(s)$. Choose an arbitrary vertex \( s \) as starting vertex for all Eulerian tours. We are going to find a bijection between anti-arborescences \( T \) converging to \( s \) and sets \( \mathcal{T}_T \) of Eulerian tours. Each set \( \mathcal{T}_T \) will have size

\[d := \deg(s)! \cdot \prod_{v \in V \setminus \{s\}} (\deg(v) - 1)!.\]

Claim 1: We can construct \( d \) Eulerian tours \( \tau \in \mathcal{T}_T \) from an arborescence \( T \), and different arborescences cannot generate the same Eulerian tour.

 Proof of claim 1: For every vertex \( v \), we number its \( \deg(v) \) outgoing edges, such that the tree edge receives the highest number. For each vertex \( v \neq s \), exactly one of its outgoing edges is a tree edge, and therefore we have \( (\deg(v) - 1)! \) ways to number them. For the root \( s \), all of its outgoing edges must be non-tree edges, and therefore we have \( \deg(s)! \) ways to number them. Therefore, given a root \( s \), we have in total \( d \) valid ways to number all the non-tree edges.

We can construct the Eulerian tour \( \tau \) using the numbering as follows: Start with trail \( \tau_1 = \langle s \rangle \). For a given trail \( \tau_i = \langle s, \dots, v_i \rangle \), select the smallest numbered unused outgoing edge from vertex \( v_i \). Continue this process until all edges have been used, and denote the resulting trail as \( \tau \).

Since the graph is Eulerian, we will not encounter any dead ends until we eventually return to \( s \). In other words, \( \tau \) must be a circuit. Thus, to show \( \tau \) is an Eulerian tour, we only need to show \( \tau \) contains all edges.

 For every vertex \( u \neq s \), if there is an edge \( (u, v) \) that has not been used, then since the in-degree of \( v \) is equal to the out-degree, \( v \) also has an outgoing edge that has not been used, so the tree edge of \( v \) has not been used either. The tree edges finally lead us to \( s \), then \( s \) also has an outgoing edge that has not been visited, which contradicts the termination condition. Therefore, no such edge is missed, and thus \( \tau \) is indeed an Eulerian tour.

Since different numberings lead to different Eulerian tours, we can construct \( d \) Eulerian tours from an arborescence, i.e., \( |\mathcal{T}_T| = d \). Also, since different arborescences lead to different numberings, they cannot generate the same Eulerian tour. $\blacksquare$

Claim 2: We can construct an arborescence \( T_\tau \) from an Eulerian tour \( \tau \), such that \( \tau \in \mathcal{T}_{T_\tau} \).

Proof of Claim 2: Each Eulerian tour \( \tau \) corresponds to a unique numbering of edges. Thus, we can construct the arborescence \( T_\tau \) by selecting the outgoing edge with the largest number for every vertex \( v \neq s \).

Apparently, there are \( |V| - 1 \) tree edges. Thus, to show \( T_\tau \) is an arborescence, we only need to show that starting from any vertex \( u \neq s \), the selected edges will finally lead us to \( s \).

Suppose there is a selected edge \( (u, v) \). As this is the last outgoing edge from vertex \( u \) and \( u \neq s \), the edge cannot form a loop, i.e., \( v \neq u \). If \( v = s \), we have shown that from vertex \( u \), the edges in \( T_\tau \) can lead us to \( s \). If \( v \neq s \), the tree edge \( (v, w) \) must have a larger number than \( (u, v) \) and \( w \neq u \). At each step, the tree edge either leads us to \( s \) or to an unvisited vertex. Eventually, we will reach \( s \).

 Hence, the selected edges form a spanning arborescence. Since \( T_\tau \) is constructed based on the numbering of edges in \( \tau \), it is always possible to reconstruct \( \tau \) from \( T_\tau \) by correctly numbering the non-tree edges. That is, \( \tau \in \mathcal{T}_{T_\tau} \). This proves claim2 and the theorem $\blacksquare$.