On this August occasion, to mark the completion of seven years of Card Colms, we break with tradition and pose a question, rather than presenting some fresh mathematically based entertainments with cards.
It's a question that's been on our mind for a long time, and we'd really like to know the answer.By a happy coincidence, this month's offering also marks our first foray into the new blog format for MAA columns, so that readers with ideas to contribute have the option of responding publically in comments below.
One, Two, Many
Humans reading this column may have noticed that for some in our tribe there are essentially three counting numbers: One, Two, Many. The last is certainly the most confusing–perhaps our inability to track three things at the same time when rushed is why we do poorly at Three Card Monte (including those versions with minimal sleight of hand).
In fact, it doesn't take much for us to lose track of even fewer objects, as tricksters of various shades have known for a long time. Paddle moves play with the brains of those of us foolish enough to think we know the difference between the two sides of an issue, and basic misdirection is all about getting people to take their eye of a single thing just long enough for the magician (or politician) to pull a fast one. There is rarely any need for smoke and mirrors.
This month's Card Colm asks a challenging question concerning the shuffling of more than two piles of cards. We may be asking too much.
In fact, it doesn't take much for us to lose track of even fewer objects, as tricksters of various shades have known for a long time. Paddle moves play with the brains of those of us foolish enough to think we know the difference between the two sides of an issue, and basic misdirection is all about getting people to take their eye of a single thing just long enough for the magician (or politician) to pull a fast one. There is rarely any need for smoke and mirrors.
This month's Card Colm asks a challenging question concerning the shuffling of more than two piles of cards. We may be asking too much.
Shove Integer
For those with a little knowledge of card shuffling, the following hypothetical exchange between two alphabetical sounding mathematicians, Aodh and Bea, may amuse:
Aodh: I've heard that seven shuffles is enough to randomize a standard deck of 52 cards.
Bea: I've heard that eight shuffles restores a standard deck of 52 cards to its original order.
This raises a tantalizing question: what magical thing happens between the seventh and eighth shuffle to restore total order from sheer chaos? That would be a very impressive effect in itself!
In fact, Aodh and Bea above are talking about rather different kinds of shuffles, though one generalizes the other.
The first statement has some validity when it refers to an irregular riffle shuffle, subject to some strong assumptions.
The second statement refers to a perfect shuffle, also known as "Faro" or "weave" shuffle, in which the deck is split in two at the middle, and the cards from the two halves are interlaced completely regularly, with the original top and bottom cards remaining in those positions (this is the so-called Out-Faro).
Riffle shuffling, in which the deck is split roughly in the middle, and the two resulting "halves" are interwoven by releasing cards from both thumbs at the same time, with no particular regularity, is a common way of mixing cards, being relatively easy to master.
A famous 1992 paper by Dave Bayer and Persi Diaconis called "Trailing the Dovetail Shuffle to its Lair" concluded that seven riffle shuffles is sufficient to randomize a standard deck. A specific measure of randomness was used, and assumptions were made about the probabilistic distribution of how the cards are split, and how the two resulting packets are "released."
Later on, others revisited this topic, with different measures of randomness and different probabilistic assumptions, reaching different conclusions. The topic continues to attract the attention of researchers, and today some argue that in fact eleven shuffles are required to really randomize a deck. This is not our concern here, so we leave it to the interested reader to pursue further, if desired.
Let's return to the idea of a single riffle shuffle, making no assumptions whatsoever about how likely the deck is to be split at or near the middle, or how regularly the cards from the two parts are dropped. All we assume is that the shuffle preserves the order of the cards within each "half": for instance, if one packet of red cards in a specific order is shuffled into another packet of black cards in a specific order, then both the red and black subsequences of the resulting shuffled deck should preserve their original orders.
Note that Lennart Green's rosette shuffle as depicted below is certainly a riffle shuffle, as we've mentioned here before. We should admit that this kind of shuffle has physical limitations governing the card mixing, so that not every possible riffle shuffle is actually achievable in this way.
[Start with two piles side by side, as shown in the first image, then use the fingers to "twirl" the left pile into a rosette; the second image shows the result. Repeat for the right pile, and then push the rosettes together. Square up the packet: it has effectively been riffle shuffled.]
It's a delightful surprise to learn that if we have a deck which
It's not hard to see that condition 2 above can be replaced with either of two alternatives: (2A) First dealing out some cards from the deck into a pile to form the second packet, instead of splitting as before, before shuffling, or, (2B) Splitting anywhere and shuffling, but then peeking at the card faces and cutting between two cards of like colour before peeling off pairs of cards.
This generalizes from cycles of length 2 to arbitrary n general as follows:
Start out with a deck of cards cycling in some regular fashion, for instance for n = 13 we might have 4 stacked repeats of these cards in (alphabetical) order: Ace, 8, 5, 4, Jack, King, 9, Queen, 7, 6, 10, 3, 2 (ignoring suits).
If some of the cards are dealt into a pile, thus reversing their order, and the resulting two packets are riffle (or rosette) shuffled together, then, we end with a deck with the property that the top (or bottom) 13 cards contain one of each value. This is the so-called Second Gilbreath Principle from 1966.
Aodh: I've heard that seven shuffles is enough to randomize a standard deck of 52 cards.
Bea: I've heard that eight shuffles restores a standard deck of 52 cards to its original order.
This raises a tantalizing question: what magical thing happens between the seventh and eighth shuffle to restore total order from sheer chaos? That would be a very impressive effect in itself!
In fact, Aodh and Bea above are talking about rather different kinds of shuffles, though one generalizes the other.
The first statement has some validity when it refers to an irregular riffle shuffle, subject to some strong assumptions.
The second statement refers to a perfect shuffle, also known as "Faro" or "weave" shuffle, in which the deck is split in two at the middle, and the cards from the two halves are interlaced completely regularly, with the original top and bottom cards remaining in those positions (this is the so-called Out-Faro).
Riffle shuffling, in which the deck is split roughly in the middle, and the two resulting "halves" are interwoven by releasing cards from both thumbs at the same time, with no particular regularity, is a common way of mixing cards, being relatively easy to master.
A famous 1992 paper by Dave Bayer and Persi Diaconis called "Trailing the Dovetail Shuffle to its Lair" concluded that seven riffle shuffles is sufficient to randomize a standard deck. A specific measure of randomness was used, and assumptions were made about the probabilistic distribution of how the cards are split, and how the two resulting packets are "released."
Later on, others revisited this topic, with different measures of randomness and different probabilistic assumptions, reaching different conclusions. The topic continues to attract the attention of researchers, and today some argue that in fact eleven shuffles are required to really randomize a deck. This is not our concern here, so we leave it to the interested reader to pursue further, if desired.
Let's return to the idea of a single riffle shuffle, making no assumptions whatsoever about how likely the deck is to be split at or near the middle, or how regularly the cards from the two parts are dropped. All we assume is that the shuffle preserves the order of the cards within each "half": for instance, if one packet of red cards in a specific order is shuffled into another packet of black cards in a specific order, then both the red and black subsequences of the resulting shuffled deck should preserve their original orders.
Note that Lennart Green's rosette shuffle as depicted below is certainly a riffle shuffle, as we've mentioned here before. We should admit that this kind of shuffle has physical limitations governing the card mixing, so that not every possible riffle shuffle is actually achievable in this way.
It's a delightful surprise to learn that if we have a deck which
- Starts out with the cards alternating red and black, and
- Is split into two parts (of any size) one of which had a red card on the bottom, the other having a black card at the bottom,
It's not hard to see that condition 2 above can be replaced with either of two alternatives: (2A) First dealing out some cards from the deck into a pile to form the second packet, instead of splitting as before, before shuffling, or, (2B) Splitting anywhere and shuffling, but then peeking at the card faces and cutting between two cards of like colour before peeling off pairs of cards.
This generalizes from cycles of length 2 to arbitrary n general as follows:
Start out with a deck of cards cycling in some regular fashion, for instance for n = 13 we might have 4 stacked repeats of these cards in (alphabetical) order: Ace, 8, 5, 4, Jack, King, 9, Queen, 7, 6, 10, 3, 2 (ignoring suits).
If some of the cards are dealt into a pile, thus reversing their order, and the resulting two packets are riffle (or rosette) shuffled together, then, we end with a deck with the property that the top (or bottom) 13 cards contain one of each value. This is the so-called Second Gilbreath Principle from 1966.
For Auto
Faro shuffling, in which the deck is split exactly in the middle, and the resulting half packets are perfected interlaced, is much, much harder to do in practice. [The key word here is practice–having once been shown for a solid hour "how to do it", by magician Mark Setteducati, a month's worth of frustrating and seemingly pointless practice suddenly led to an irreversible breakthrough.] If the top and bottom cards always remain in position—so that we are doing an Out Faro—it is well known that exactly eight such perfect shuffles restores a deck of 52 cards to its original order.
A great deal of impressive card magic has been developed by those who've mastered Faro shuffling, some of which can be adapted to the easy-to-handle inverse operation of dealing cards into two piles alternately. A great deal indeed!
S. Brent Morris has a terrific book Magic Tricks, Card Shuffling, and Dynamic Computer Memories from 1998 which not only surveys all of the key mathematics of such Faro shuffles, but also explores the mathematics resulting from three packets being perfectly interlaced (and he gives advice on how to do that in practice).
There is a question begging to be asked here.
A great deal of impressive card magic has been developed by those who've mastered Faro shuffling, some of which can be adapted to the easy-to-handle inverse operation of dealing cards into two piles alternately. A great deal indeed!
S. Brent Morris has a terrific book Magic Tricks, Card Shuffling, and Dynamic Computer Memories from 1998 which not only surveys all of the key mathematics of such Faro shuffles, but also explores the mathematics resulting from three packets being perfectly interlaced (and he gives advice on how to do that in practice).
There is a question begging to be asked here.
Restores Teeth
Since a Faro shuffle is a special case of a riffle shuffle—the neatest possible type—it follows that anything promised by the Gilbreath principles will also hold for a deck which has been Faro shuffled, with bells on.
This brings us to our burning question (brusque intoning):
Is there a way to pre-arrange a deck and split it into three (or more) parts
so that some structure remains when they are "riffle shuffled" together?
Perhaps, following Lennart Green, a triple rosette shuffle of some sort can be executed on three parts of a deck so that the result is not totally chaotic? What kind of pre-arrangement would be required?
Bear in mind that card reversal of one packet is not required when riffle shuffling a pre-arranged deck in the usual way, in order ro retain some predictability, as we saw here two years ago in The Bligreath Principle.
If periodic cycling of some sort is appropriate—as it is in the case of splitting the deck into two packets before riffling—would the cycle length need to be a multiple of six? It seems that we must cover the case where two of the parts are riffled in the usual way and the third is merely appended at the top or bottom, which leads us to suspect that the cycle length must include factors of 2 and 3.
Most importantly, is there any hope of finding an application to card magic?
Or is it simply a case of one too many packets to shuffle?
We'd love to hear from readers with ideas on this topic. Please feel free to use the comment option below.
"Need rot sextet" is an anagram for "extend rosette," "shove integer" is an anagram for "seven or eight," "for auto" is an anagram for "out faro," "restores teeth" is an anagram for "three rosettes," and "brusque intoning" is an anagram for "burning question."
This brings us to our burning question (brusque intoning):
Is there a way to pre-arrange a deck and split it into three (or more) parts
so that some structure remains when they are "riffle shuffled" together?
Perhaps, following Lennart Green, a triple rosette shuffle of some sort can be executed on three parts of a deck so that the result is not totally chaotic? What kind of pre-arrangement would be required?
Bear in mind that card reversal of one packet is not required when riffle shuffling a pre-arranged deck in the usual way, in order ro retain some predictability, as we saw here two years ago in The Bligreath Principle.
If periodic cycling of some sort is appropriate—as it is in the case of splitting the deck into two packets before riffling—would the cycle length need to be a multiple of six? It seems that we must cover the case where two of the parts are riffled in the usual way and the third is merely appended at the top or bottom, which leads us to suspect that the cycle length must include factors of 2 and 3.
Most importantly, is there any hope of finding an application to card magic?
Or is it simply a case of one too many packets to shuffle?
We'd love to hear from readers with ideas on this topic. Please feel free to use the comment option below.
"Need rot sextet" is an anagram for "extend rosette," "shove integer" is an anagram for "seven or eight," "for auto" is an anagram for "out faro," "restores teeth" is an anagram for "three rosettes," and "brusque intoning" is an anagram for "burning question."
@JohnAllenPaulos ( https://twitter.com/#!/JohnAllenPaulos ) tweeted a very nice way of expressing the basic binary Gilbreath Principle from 1958:
ReplyDelete"2 car lanes, 1 Black/White, B/W, etc, 1 W/B, W/B, etc. However they merge into 1-lane tunnel, 1st, 2nd, nth pair emerging are opp. colors."
Of course this generalizes (a la Gilbreath 1966) as follows: 2 lanes of cars, one repeating Red, White, Blue, Green, White, Orange, the other repeating Orange, White, Green, Blue, White, Red, however they merge, will yield a single stream of cars in blocks of six, each block consisting of one each Red, Blue, Green and Orange, and two White (in some order within each block).
My "Big Question" from August above then becomes, what kind of regularity can we impose of 3 or more merging lanes of cars, so that the single merged stream will have some predictability, regardless of how the merging is done?
I only know the answer in the case of Faro or perfect merging.
Does anyone have any ideas here?
Maybe it's not a coincidence that Gilbreath 1966 sounds like a model of car: the word "auto" did turn up, automagically as it were, in the August Car Colm:-)