Friday, August 30, 2013

Rosette Shuffling Multiple Piles

Mathematical Card Magic: Fifty-Two New Effects (AK Peters/CRC Press) is finally out. It has sizable overlap with the past nine year's worth of Card Colms here—about 75%?—but is organized quite differently. It's also written for a wider audience and generally avoids technical language. What follows is a taster of one of the nagging questions addressed in it, first publicly raised two years ago in A Call For A New Shuffle Principle (Need Rot Sextet?).

Limit Plus Peel

Some observations and assertions of a mathematical nature are easy, or at least routine, to generalize from two to three or beyond. Others are trickier (e.g., cake cutting), and a few turn out to be impossible (e.g., angle trisection using only a straightedge and compass). In the August 2011 Card Colm mentioned above, we made an appeal for a new kind of generalization of the ever-popular Gilbreath shuffle principle, asking

Is there a way to riffle shuffle three or more piles of prearranged cards
and expect some order to remain, without assuming perfect interweaving?

The good news is that this month we have something to report along these lines. We can now sleep at night, although a really impressive magic application is still proving elusive.

Treeless Shutoff

First it pays to switch our focus from riffle shuffling—which in the Gilbreath context follows the dealing out of some cards from a packet to form two piles—to something equivalent to that, which has a more obvious generalization to three or more piles. We're referring to Lennart Green's rosette shuffle as depicted below. Two side-by-side piles are twirled into rosettes with the fingers before being pushed together and squared up.



When we say that this is equivalent to riffle shuffling we really mean that the following internal coherence or solitaire principle applies.
  • If two piles of cards, running Ace to King of Hearts and Ace to King of Spades, respectively, are riffle or rosette shuffled together, and the cards in the resulting packet are dealt one at a time into two piles separated by suit, then the original piles will be reformed, in reverse order.
In other words, we'll never be faced with dealing the 7 of Hearts onto a Red card other than the 6 of Hearts. By the time we get to that 7, we can be sure that the Ace, 2, 3, 4, 5 and 6 of Hearts will already have been dealt, in that order.

Sheaf Bullfighters

In the first August edition of Card Colm, back in 2005, we explored the first (or basic) Gilbreath principle from 1958, which concerns the structure retained when two piles of cards are riffle or rosette shuffled, assuming that we start with an alternating packet of some kind and then deal "about half" of the cards to the table to give rise to the two piles. Generalizing that to situations where the packet started by repeating a cyclic pattern of length greater than two leads easily and naturally to the second (or generalized) Gilbreath principle from 1966, which we covered here in August 2006.

In a nutshell, the Gilbreath Principle says that
  • If we start with a packet of sm cards that consists of m repeated stacks of a particular set of s cards, each set being in the same fixed order with respect to some characteristic of interest (such as color, suit, or value), and we count out some of these to the table—thereby reversing their order—and then riffle shuffle together the two resulting piles, we're sure to get a packet in which each stack of s cards pulled off the top contains exactly one card of each of the key types, in some order.
The basic case is when s = 2. If the cards alternate Red and Black, over and over, at the outset, then the shuffled packet has the property that the cards in positions 1-2, 3-4, 5-6, etc, are always of different colors, though we can't say in which order Red and Black cards occur in each such pair.

For the case s = 3, we could start with a packet consisting of trios of Spades, Diamonds, and Hearts, in that order, over and over. The shuffled packet then has the property that the cards in positions 1-3, 4-6, 7-9, etc, always consist of one each of those three suits, again in some order. When s = 13, starting with a packet consisting of four stacks of the thirteen card values, in the same fixed order, we end up with four clumps (the cards 1-13, 14-26, 27-39 and 40-52) consisting of the thirteen values in some mixed order.

Lovely though all of this is—and it has spawned a ton of magic over the last half century—it's well-explored territory. What more is there to say? Persi Diaconis & Ron Graham give a complete characterization of such matters in what they call The Ultimate Gilbreath Principle on page 70 of their beautiful, inspirational and prize-winning book  Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks (Princeton University Press, 2011). Some Gilbreath variations were considered here in subsequent Augusts, in The Bligreath Principle (2009) and Gilbreeath Shuuffling (2012). Just six months ago we couldn't resist sharing a new twist on all of this due to John Hostler in Flushed with Embarrassment (February 2013). Normal Gilbreath's own long-awaited book is coming soon, from L&L Publishing.

But there is another direction in which to turn, in search of a different kind of thrill. What if we rosette shuffle three or more piles with some simple structure?



Certainly, the earlier solitaire principle extends in the obvious way:
  • If k piles of cards, running 1-n, representing k "suits," are rosette shuffled together, and the cards in the resulting packet are dealt one at a time into k piles separated by suit, then the original piles will be reformed, in reverse order.

Canonical Indecencies Pix

Now we highlight something Karl Fulves pointed out in his hard-to-find book Riffle Shuffle Set-Ups (1968), which saw distribution only in magic circles. The rosette shuffle wasn't on his radar screen, of course, he was thinking in the context of riffle shuffling multiple piles, say, two at a time, until he had a single packet again. Even for the case of two piles, this fact has languished in obscurity for decades.
  • If k piles of cards, running 1-n, representing k "suits," are rosette shuffled together, and the cards in the resulting packet are peeled off k at a time, then if the jth set matches in value, they have value j.
In other words, if we rosette the four suits of a standard deck together, each having started in the order Ace to King, and we find that the third, seventh, and eleventh quadlets pulled off the top all match across the board, then they must consist of the 3s, 7s, and Jacks, respectively.

In practice, this is better performed with the suits arranged in some less obvious but memorized order. For instance, suppose we use the starting arrangement 3, 5, 10, Ace, 9, Jack, 2, 8, 7, Queen, 6, 4, King, in each suit. (This is much favored by John H. Conway, and is based on the mnemonic "The Five Tenacious Boys Nicely Joke To Hated Servant Girls Sick For Absent Kings"—we've omitted Jokers.) Have an audience member twirl the four face-down suit piles and mush them together, then turn away and request that cards be peeled off four at a time and inspected. If any such quadlet matches, you are informed. If the fifth and eighth quadlets match, say, "Coincidences I can explain." Confidently announce that they are the Jacks and 8s, respectively.

Incidentally, Fulves also has something to say about the values in any situation where the jth set of k cards contains of one of each suit (with none repeated).

Arrange Wall Modish

A year ago—and a full year after we issued the Call For A New Shuffle Principle (Need Rot Sextet?)—Ron Graham graciously responded to repeated prodding by coming up with the following key breakthrough, shared here with his kind permission.
  • Arrange a packet in cyclic order 0, 1, 2, 0, 1, 2, .... Now split into three piles that have as their top cards, 0, 0, and 1. In other words, the cards in the three piles are in the order 0, 1, 2, 0, 1, 2, ..., 0, 1, 2, 0, 1, 2, ... and 1, 2, 0, 1, 2, 0, ... . Rosette shuffle them together, so that in the result, the relative order of the three piles is preserved. Start removing sets of three consecutive cards at a time. Then none of these three-card sets will have all values the same.
That's not to say that three cards of the same type can't end up together, one coming from each pile, but they won't all be in any one of the triplets 1-3, 4-6, 7-10, and so on; they'd have to straddle two such triplets. More generally, Graham offered the following, which we think of as a kind of Non-Alliance Principle:
  • Start with a packet arranged cyclically as 0, 1, ..., , s-1, 0, 1, ..., s-1, and then break it into s piles, and rosette shuffle those together. If we now remove sets of s cards at a time from the top, and the top card of the original ith pile is denoted by ai, then assuming the sum of the ai is not 0 (mod s), we can be sure that none of the sets of s cards will have all values the same.
For s = 2, this is equivalent to something we have known for a long time. It says that if we break an alternating packet into two piles whose top cards don't match and then rosette shuffle, we can be sure that the cards in positions 1-2 won't match either, and likewise neither will those in positions 3-4, 5-6, and so on. This is the basic Gilbreath principle once more: the careful splitting suggested here is a quick alternative to the usual dealing out of cards to form the two piles (a shortcut which only works for alternating packets).

For s = 3, start with a packet cycling Clubs, Hearts, and Diamonds, and split it into three piles that have as their top cards Clubs, Clubs, and Hearts. Rosette shuffle, and pull cards off the top three at a time. No such triplet will consist of three cards of the same suit. The same conclusion also holds whenever the top cards of the three piles account for exactly two of the three suits in play. The principle is not saying anything when the top cards of the three piles are all the same, or account for one of each suit; but perhaps those cases yield to a different kind of analysis.

More details—and a preliminary magic application—can be found in Chapter 8 of Mathematical Card Magic: Fifty-Two New Effects (AK Peters/CRC Press, 2013).

"Limit Plus Peel" is an anagram of "Multiple Piles," "Treeless Shutoff" is an anagram of "Rosette Shuffles," "Sheaf Bullfighters" is an anagram of "Gilbreath Shuffles," "Canonical Indecencies Pix" is an anagram of "Coincidences I Can Explain," and "Arrange Wall Modish" is an anagram of "Ronald Lewis Graham."