Friday, August 31, 2012

Gilbreeath Shuuffling

For many years I drove a car whose audio system had a "source" setting which offered a choice of C (for CD), R (radio) and A (auxiliary, which turned out to work with an mp3 player), only accessible via a one-way loop button. Toggling (troggling?) between them seeking the desired option, while keeping one eye on the road, was not ideal. I could never remember what order they cycled through, until one day it dawned on me that there were only two possibilities, and I also noticed that the manufacturers had thoughtfully arranged them as C-A-R over and over. From then on, I could change the source quickly and accurately while driving without risking life and limb by looking down.

This real life manifestation of the fact that (up to rotation) there are (n-1)! ways to arrange n things in a circle came to mind when analyzing "ESP + Math" from page 48 of More Self-Working Card Tricks by Karl Fulves (Dover, 1984), which we present below in slightly modified form. That tome is one of four from the same author and publisher which are devoted to card tricks many of which have mathematical underpinnings.

Fulves has the reader assemble two packets of 12 cards side by side and then riffle shuffle them together. From the top down, the first packet consists of four rounds of Spades, Hearts, Diamonds in that order (any values). The second packet consists of four rounds of Spades, Diamonds, Hearts, in that order (any values). No Clubs are used, and the card values play no role.

Suppose, for instance, that the first packet is set up as: K♠, 5♥, 9♦, 8♠, J♥, 3♦, 5♠, 8♥, 7♦, A♠, A♥, 5♦, and the second packets is set up as: 3♠, 10♦, Q♥, 7♠, 4♦, 10♥, 9♠, K♦, 6♥, 2♠, 2♦, 7♥. When riffle shuffled, the reader ends up with a packet of 24 cards. The display below shows one possibility from top to bottom, considering the second row of 12 as following on from the first:

 Click to enlarge

If cards are now peeled off three at a time from the resulting face-down packet, then a curious pattern emerges. Of course, in the above example, the shuffling can't have been very even, as the first five cards displayed clearly came as a clump from one of the initial packets of 12 cards. Hence, the first three cards feature one of each suit.

Consider the next three cards: there are two Spades, and one of them is the first card of this triple. There is no Diamond. The next three cards contain two Diamonds, one of them in the first position, and there is no Heart. The fourth group of three cards contains one of each suit, so ignore it. The next group of three, which starts the second line in our display, contains two Hearts, one in the first position, but no Diamond is present. In fact, no matter how the riffle shuffle turns out, a general prediction principle applies:

Ignoring consecutive triples in which each of Diamonds, Hearts and Spades are present,
there is a cascading sequence of deductions that can be made: the first triple with a suit
repeated features two Spades, and one of them is the first card in that triple. Whichever
suit is not represented appears twice in the next triple with a suit repeated, and one of them
is the first card in that triple. This logic repeats as long as triples with repeated suits show up.

Note that above we are referring to just the eight consecutive triples which arise starting with the first card, not to "running triples." The claims made also hold for any two packets whose sizes are multiples of three, with suit cycling as described.

Why does this work? Before answering, we present a variation which might engage audiences more. It also aims to reduce the likelihood of getting any triples in which all three suits are present.

We then look at the mathematics behind it, and extend from cycles of length three to cycles of length four (or more). It turns out that the case of cycles of length two---which doesn't lead to an interesting effect in our context---derives from the original Gilbreath principle of 1958 Hence, in essence, what we have here is a generalization of that principle. It's related to, but distinct from, the broader Gilbreath principle from 1966.

Guessing Game

First, let's agree to mix the cards a little differently, using Lennart Green's rosette shuffle. Combinatorially, it's equivalent to the riffle shuffle suggested above: the cards within each packet of 12 remain in their original order when considered within the final packet of size 24.

Here's how to do this. With the two packets side by side, use the fingers to "twirl" the left one into a rosette, repeating for the right one, and then push the rosettes together. The images show the sequence of moves. Finally, square up the resulting packet.

 Click to enlarge.
Applying this to the two original packets of 12 cards above, and taking care to ensure that the top cards of each packet end up together, we may end up this packet of 24 cards:
 Click to enlarge.

As is easily verified, the prediction principle does not let us down, although once again two of the eight triples contain cards of all three suits. (We have found through experimentation that the rosette shuffle very often results in fewer than two such triples.)

Here's a way to take advantage of this principle. Deal the packet of 24 shuffled cards into three piles from left to right. Retain the first one for yourself, and give the others to two spectators. Request that each person deal into a pile on the table to verify that they have eight cards, while doing likewise yourself; this is actually a ruse to reverse the order of each pile.

Next, suggest that a guessing game be played. Have each spectator guess the suit of the top card in their respective piles, before turning them over. You already know that one of them is a Spade, so that if the first person's card turns out to be something different, you can even guess that the next person's is a Spade. In any case, you end up by correctly guessing that yours is a Spade before you turn it over to confirm. Chances are, you'll do much better than the spectators who have absolutely nothing to go on, and don't even realize that there are no Clubs in play! Have those three cards set aside face down, quietly noting which suit you did not just see, and proceed to the guessing and uncovering of the suits of the next three exposed face-down cards. After a few successful rounds say, "Perhaps you think I need to see your card faces to guess mine correctly? This time let's all guess before anyone exposes their cards!" You still come out ahead most of the time, despite the misdirection of the words you just uttered. In the hopefully rare cases where all three cards are of different suits, so that your reasonable guesses are wrong, modestly say, "Nobody's perfect all the time."

Given the visibly shuffled state of the cards, your audience should be baffled (and impressed) by your near-perfect predictive powers.

Mathematical Games

So what is the mathematics behind all of this? Let Spades, Hearts and Diamonds be represented by 0, 1, 2, respectively, so that the packet of the left, from top to bottom, is 012012012012, and the packet on the right is 021021021021. Here's the key observation:
The effect of riffle (or rosette) shuffling these two and then pulling off three cards at a time, is to, (A) line up the left packet in reverse beside the right one to get 210210210210 021021021021, and (B) successively extract three adjacent cards "from the middle", starting by including at least one of the two initially adjacent 0s. Ignoring the undesirable cases where all three cards come from one of the packets, we therefore get as our first triple either two 0s and a 1, with a 0 on top, or two 0s and a 2, with a 0 on top.

In the first case, the next triple---again assuming it involves cards from both packets---will be extracted from the middle of 2102102102 21021021021, and hence consist of two 2s (and a either a 0 or a 1). In the second case, the next triple will be extracted from the middle of 21021021021 1021021021, and hence consist of two 1s (and a either a 2 or a 0). Now the pattern which gives rise to the claimed prediction principle should be clear.

Mega Guessing

For a version with groups of four cards each time, arrange two packets of say 16 cards, one cycling Spades, Hearts, Clubs, Diamonds, from the top down, and the other cycling Spades, Diamonds, Clubs, Hearts.

Mathematically, from top to bottom, we have 0123012301230123 on the left, and 0321032103210321 on the right (the suit/numerical correspondence has changed from what we had above). This time, we can assert:

The effect of riffle (or rosette) shuffling these two and then pulling off four cards at a time, is to, (A) line up the left packet in reverse beside the right one to get 3210321032103210 0321032103210321, and (B) successively extract four adjacent cards "from the middle", starting by including at least one of the two initially adjacent 0s. Ignoring the undesirable cases where all four cards come from one of the packets, we therefore get as our first groups of four cards either two 0s, a 2 and a 1, or two 0s, a 1 and a 3, or two 0s, a 3 and a 2. In all three cases there is a 0 on top, and the next (worthy!) group of four contains two cards of the suit not represented in the previous group of four.

The same kind of effect as before can be pulled off here: have the 32 cards dealt into four piles of four, then re-dealt to reverse the card order. Now, if you claim the first such pile for yourself, you can correctly predict the suit of most of the those cards provided that you progressively get to see the corresponding cards in the other three piles. The guessing game is a good and distracting way to achieve this.

The principle extends to five or indeed any larger number. Readers may like to try out a version with cycles of length 13.

Clopening Remarks

Question 1: Is it mandatory to reverse the order of each pile? What if one were to work up from the bottom of the original packets instead of down from the top, perhaps modifying the packet set-up accordingly?

Question 2: Is a there way to take advantage of the card values as well as suits, to improve the accuracy of the predictions made?

Question 3: Are there other such variations on the Gilbreath principle, for cycles of length four or more, of interest? Perhaps shuffling a packet cycling Spades, Hearts, Clubs, Diamonds, from the top down, with one cycling in some order not considered above (or below)?

Question 4: Have we really exhausted the possibilities for cycles of length three, notwithstanding our starting C-A-R comments? After all, there are other arrangements of the two starting packets relative to each other! One of them fits in with the Bligreath Principle discussed here in August 2009.

We finish by pointing out a connection between what we have considered and the general Gilbreath shuffle principle. Let's first review the latter, via a standard effect which is to stack a deck with the suits cycling in some fixed order, then deal out about half of the cards to form a pile, before riffle shuffling those into the remainder. Pulling off four at a time, one is guaranteed to have all four suits represented each time, though in what order is anyone's guess.

Mathematically, that's equivalent to starting with something like 301230123...0123 in one pile (those cards retained in the hand) and 2103210...3210 in another on the table. The effect of riffle (or rosette) shuffling these two together and then pulling off four cards at a time is to reverse one of those piles and place it beside the other yielding 3210...321032103 2103210...3210, and then extract four cards at a time, starting "in the middle" with either the 3 or 2 (or both) which abut the visible gap above, along with several adjacent cards. Each time one must get one of each of the four types.

A similar connection exists between the "ESP + Math" effect and the Gilbreath principle for packets consisting of repeated cycles of length three.

When all is said and done, what we have explored above is the case of inserting one additional "repeated" card near the middle, beside one of the same type, in the usual Gilbreath context, and then proceeded to riffle or rosette shuffle. While it changes the nature of one's prediction, predict one certainly can; at least for a quarter (or a third) of the shuffled cards, modulo those annoying cases where all types are represented in the groups pulled off.

Instead of starting with the effect in the Fulves book and extending it from cycles of three cards to cycles of four cards, what happens if we consider cycles of two cards? It turns out that we are basically revisiting familiar Gilbreath terrain. Without loss of generality, we are riffle (or rosette) shuffling together two packets of the same type, each cycling Black Red over and over from the top down. The effect is predictable and well-known (and is covered in the Fulves volume referenced above), as it's just a basic "out of synch" Gilbreath shuffle of the type first published in 1958. It is customary to "restore" such shuffled packets to the usual post-Gilbreath state by splitting between two cards of like colour, after which each pair pulled off definitely consists of one Black and one Red card, in some order. However, if this step is skipped, then each pair which doesn't consist of one card of each colour instead consists of two of the same colour, starting with two Blacks, then two Reds, etc. This is no great surprise, and is hard to make into an engaging effect; for one thing, Black/Red or Black/Red pairs occur here with great frequency. (The only interesting part is the alternation of the colours when two like-cards are paired up. Of course one will never encounter more than two adjacent cards of the same colour; something which characterizes a packet in post-Gilbreath mode.)

In conclusion, inspired by "ESP + Math" from the 1984 Fulves volume, we have suggested a generalization of the binary (k = 2) Gilbreath principle published in 1958. It's different in spirit from the more general (arbitrary k) Gilbreath principle published in 1966, though it's closely related to it.

Many other shuffle variations may be found (so to speak) in the hard to find book Riffle Shuffle Set-ups, also by Karl Fulves (1968).

The positioning of repeated cards near the middle of the shuffled packets above prompted our tongue-in-cheek title, Gilbreeath Shuuffling, which we recommend be pronounced gil-BREEATH SHOE-fling to distinguish it from the more normal GILL-br'th shuff-l'ng.