I used to do magic tricks as a child (in fact, I even wrote about the connection between magic and computer science on my college essays). Today, not so much. But as a math and CS student that occasionally stumbles upon viral videos of card tricks, I find myself still astounded by how much mathematical structure underlies many of them. Today we will explore a simple yet baffling principle that sneaks up on unsuspecting victims, even those trained on its existence or nature.
The Gilbreath Principle is, more rigorously, a series of mathematical theorems, the first few of which were proposed by Norman Gilbreath. In this article, we will start with a generalization, and move backwards. But before we can do that, we must establish the concept of a Gilbreath Shuffle.
A Gilbreath Shuffle operates in three steps. First, you deal out a few cards from the top of a deck of cards, effectively reversing the order of this portion. And then, you riffle shuffle the two piles together. What this does is construct a list of cards, combined from the two sub-piles with the two piles as subsequences.
More algorithmically, we can represent the procedure as follows:
GILBREATH-SHUFFLE(n, k): // where 0 < k < n
0. Begin with an array of integers A = [1, 2, 3 ... n]
1. Split the sequence into two subarrays: A1 = [1 ... k] and A2 = [k + 1 ... n]
2. Reverse the first subarray, so it is now A1' = [k ... 1]
3. A' = MERGE-ARRAYS(A1, A2)
4. return A'
The method MERGE-ARRAYS(A1, A2) merges the two arrays. It creates the final array A' of length n such that A1 and A2 are subsequences. The way to do this is to riffle shuffle the arrays together. More rigorously, at each step, from 1 to n, you choose one of the arrays A1 and A2, and pop the head of said list. You then append the popped element to A'. If a source list is empty, then that list cannot be chosen. All this (in both methods) is easily accomplished by using deques:
MERGE-ARRAYS(A1, A2):
0. Let A' = []
1. FOR i in [1 ... n]:
2. Choose a nonempty array X from within {A1, A2}
3. let z = X.front()
4. X.pop()
5. A'.push(X)
6. ENDFOR
7. return A'
Now, we are ready to begin our journey. The first stop is what we call the Ultimate Gilbreath Principle, which goes something like this:
The proof sketch is by induction, by following the method. Prefixes of A' can be thought of as the intermediate states of A' during the MERGE-ARRAYS method. Recall that A1 begins as [k ... 1] and A2 as [k + 1 ... n]. The action of popping from the front of an array can actually be equivalently represented as maintaining a pointer that starts at 1 and goes up to n. Each time we pop, we retrieve the value (e.g.) A1[ptr], and subsequently incrementing the value of ptr.
So, let p1 and p2 represent the indices of the original forms of A1 and A2 respectively, containing the current top element. So at the start, p1 = p2 = 1. After, say, popping A1, p1 becomes 2. The next pop sets p1 to 3. And if A2 is popped, p2 independently increments to 2, and so on.
The values of A1[p1] and A2[p2] are the heads of the arrays. But what we will maintain here is that A1[p1] is one less than the minimum element in A' at each step, and A2[p2] one more than the maximum at each step. The only exception is when A' is empty.
Base case: if we pop A1 first, then A1[1] = k is both the max and min in A'. Then, A1[2] = k - 1 and A2[1] = k + 1 satisfy this invariant. If A2 is popped first, then A' contains only k + 1, and A1[1] = k, and A2[2] = k + 2 similarly satisfy the invariant.
Now for induction. After some step (at least one iteration), we have popped all elements in A1[1 : p1 - 1], and A2[1 : p2 - 1] (if ptr - 1 = 0 then consider the most recent popped element to be at index 0). The heads are now A1[p1] and A2[p2]. Because of the structures of A1 and A2, we know that A1[p1 - 1] and A2[p2 - 1], the most recently popped things, are also the minimum, and maximum, of the growing A'. Then, naturally, if we assume the current state of A' to contain a permutation of consecutive integers, then the next popped value is consecutive with either the maximum or minimum of A'. Thus, the state of A' after this step is also containing only consecutive integers.
And for the cases where we have not popped anything from some list (e.g. we only popped from A1 thus far), the condition still holds, since the head of the that list is consecutive with the minimum or maximum of A', which was the first head of the other list.
So that's the proof of the most important part. We will now quickly prove a small corollary which segues neatly into the more classical version of Gilbreath's Principle:
The proof is rather simple, also by induction. The first s elements naturally form one of each residue, since they are a collection of s consecutive integers. Now, for s and i, it is rather trivial to prove that, since A[1 : s * i] contains s * i consecutive integers in some order, then naturally there are i of each residue mod s in said list. Thus, comparing the lists A[1 : s * i] with A[1 : s * (i - 1)], the difference is A[s * (i - 1) + 1 : s * i], which must contain one of each residue mod s.
Now, we get into the actual card magic. Begin by arranging a deck of cards such that the colors alternate red and black. Deal out some number of cards from the top, and riffle shuffle the two piles together. Now, if you take off pairs of cards from the top, you will miraculously find that each pair contains one red and one black card. This is an obvious corollary of the ... corollary we proved above for the case s = 2. In fact, this is actually Gilbreath's original proposition:
This can also be exploited with, say suits (s = 4). Arrange the cards so the suits repeat in 13 blocks. Then, a Gilbreath shuffle preserves the 13 blocks of different suited cards, each in whatever order.
Some common ways to use this principle as the underlying structure of a card trick include making it a "game" between the performer and the spectator. Instead of directly peeling off pairs, per say, you could instead, deal alternating cards into two piles, creating two sub-piles of cards that exactly are color inversions (top cards are different colors, and so on). Then, you can perhaps deal your cards into red and black piles and ask your spectator to mirror your actions face down. The end result, naturally, separates all piles into homogenous color.
There are countless effects that rely on the Gilbreath Principle to trip up unsuspecting victims, too many to count. You should be able to find some online. The YouTube channel Absolute Math Magic (ran by an actual math professor) has tons of these.