The Gilbreath Principle

The Ultimate Gilbreath Principle

For a sorted (integer) sequence [1,2,\dots,N] , split it into two subsequences which are A=[1,2,\dots,k] and B=[k+1,k+2,\dots,N] . Reverse sequence A into A'=[k,k-1,\dots,1] , then riffle shuffle A' and B together (which means, randomly insert elements of A' into B , while ensuring the internal order of elements within both sequences remains unchanged) and obtain a sequence \pi .

\forall j , first j elements in \pi can always form a consecutive sequence of integers.

Proof

Take a close look at A' and B

When randomly inserting elements from A' into B , we are actually choosing the first element from either of the sequence and queue it into the new sequence. For example, we choose k from A' first and queue it into a new sequence \pi .

Then queue the element k+1 , k+2 from B into \pi (just ramdomly choosing the elements)

When choosing elements like this, we actually have chosen an element as the 'pivot' on the number line. Then what we are actually doing is that we are choosing the direction we are extending on the next turn. In this example, if we choose element from A' , we are adding the integer immediately to the left of the interval covered by the sequence \pi ; if the element is from B , the added integer is immediately to the right of the existing interval. So our interval of integers are 'spreading' to either side when j is increasing. This is consistent with the concept that for all j , first j elements can form a consecutive integer sequence.

In most magic textbooks, the ultimate Gilbreath principle appears after other variants of the Gilbreath principle. This is because the ultimate one is less important and less useful in practice. The reason why I introduce this principle first is that it can actually help us understand the basic pattern of the original Gilbreath principle.

Variants

If we use [1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5] as the initial sequence instead, we will find some interesting pattern. Randomly split the sequence and reverse one:

Assume we obtain \pi and

Look at elements in \pi in group of five

are all \{1,2,3,4,5\} in some order.

This is because on the number line of 1,2,3,4,5,1,2,3,4,5,\dots , any five consecutive integers must contain all the numbers in \{1,2,3,4,5\} . When we choose a pivot, spreading the interval will always cover five distinct numbers first, and then the next group of numbers, and then the next group and the next group.

If we use [1,0,1,0,1,0,1,0,1,\dots] , \pi would be like

which are severval 1 pairs (or 10 pairs). For any k , sequence [1,2,\dots,k]\times m can always produce a Gilbreath permutation, where groups of k elements (starting from the first element) contains all numbers in \{1,2,\dots,k\} .