Monday, December 24, 2012

Predictability Outranks Luck

In this 12th month of '12, on the eve of the start of the 12 days of Christmas, we revisit a topic explored 12 years and 12 weeks ago, which appeared online as part of AMS's What's New in Mathematics (October 2000).

It concerns a variation of a surprising convergence result which was discovered by physicist Martin Kruskal in the 1970s, as popularized in card form by Martin Gardner. It can be found on page 274 of the latter's book Penrose Tiles to Trapdoor Ciphers (W.H. Freeman, 1989).

It's a fine example of a baffling effect in which a spectator initiates a random process, based on mentally selecting a secret number known only to him or her, yet you can almost certainly correctly predict the ultimate outcome.

Let's start by reviewing the classic incarnation. Shuffle a full deck of cards, then decide on a number k between 1 and 10. Slowly deal out the cards into a face-up pile, noting the card in position k, called the first key card, and using its value, counting out to the next key card, whose value is in turn used to count out to the following key card, and so on.

For instance, if k = 6, and the sixth card is a 9, then that's the first key card and the second key card would be the fifteenth card. Repeat as often as is possible. Here, it's conventional to agree that the royal cards (Jack, Queen and King) have a common low value, such as 5.

Eventually you arrive at a key card---perhaps the last card in the deck---from which you can't go any further, as it's not followed by enough cards to permit the next required count out. This final key card is the one to note; unless it's the final card we can think of it as a sticking point, or road block.

Of course its location depends on the particular order of the cards in the deck at the outset, and the choice of k.

What is quite unexpected is that, for a given deck order, no matter what value k has, we arrrive at the same final key card. More precisely, averaged over all possible shuffled decks, this occurs with probability about 5/6.

A proper analysis of this takes us into Markov chains and stochastic processes, but we'll provide a basic probability estimate later on, for the version we suggest, to convince you that it's not so unreasonable.

Predictable Road Block

Here's a new way to present this as a prediction effect.

Take out a deck of cards and carefully demonstrate the counting-out-the-deck principle, based on a randomly chosen number between 1 and 10 which you have an audience member call out. You can spin a yarn about the 52 cards representing a long trip, just making sure that everyone understands the importance of getting as far along the road as possible, either to the very end or until a road block impedes progress.

Now have a spectator thoroughly shuffle the deck, and then take the cards back. Rummage through them, face up, announcing that things will go much faster if only the low values are used. Pull these out as you encounter them, dropping them into a face-up pile on the table.

Hand the spectator the resulting packet of small-valued cards, now face down, and turn away. Ask for a random number between 1 and 6 inclusive to be decided on, secretly. A die could be rolled to determine this. Have the spectator use that number to initiate the process you demonstrated earlier. The spectator does this, and deals cards from the packet accordingly, until arriving at the sticking point (or the end). Have that card set off to one side face down.

Now turn back, and stare intently at the back of that card. Say, "I could be wrong, but my gut feeling is that you got as far as ....", where upon you name a specific card. Have the face-down card exposed, with any luck you nailed it.

How do you pull this off?

Before you demonstrate the counting procedure, run through the deck and dump the Jacks, Queens and Kings, adding, "to save confusion" (which is true).

Be sure to emphasize that when the spectator later deals cards to a pile, it should be done steadily so as to give no hint as to the location of any of the key cards. Say, "I'll be turned away, but I have very sensitive ears." (People do tend to deal noisily and with obvious pauses!)

Once you are convinced that the directions are well understood, have the deck shuffled once more. Take it back and say, "To speed things up, let's only use about half of the deck, say the the Aces to sixes." Now start to extract those cards openly.

Here's the secret: as you pull those twenty-four face-down cards out, dropping them one by one into a pile, you follow the same instructions that you just gave!

Choose your own secret number between 1 and 6 and then, brazenly and on-the-fly, determine your key cards in the growing pile, working from the bottom up. Yes, it requires a quick mind and steady nerves, but it's doable. The mathematics suggests that you'll probably arrive at the same sticking point or road block as the spectator will in due course, or else you'll both make it to the end. (Admittedly, it's best if the last card seen here doesn't end up being the one the spectator gets to.)

Actually, forget picking a number between 1 and 6, simply pick a very low valued card among the first few as they emerge from the shuffled deck, say a 2 in the third position from the bottom of the pile you build up, and go from there. Of course, the spectator will probably start from a different card, once you have handed over the 24-card packet face down, but you'll quite likely reach the same destination.


For instance, imagine that the twenty-four cards in the packet are in the order displayed above, read row by row from left to right. Try using any of the first six cards as the starting point. If the Ace of Hearts is used, then the next image shows the resulting key cards highlighted relative to the rest. Evidently, the road block is the 5 of Diamonds.


As mentioned above, we recommend making your choice small in value and early in the packet: if possible, favor an early Ace or 3 over a 4 or higher in position four or five or six.

As it happens, with the arrangement considered above, all choices of starting point lead to the 5 of Diamonds. It's the common sticking point.

In general, you and the spectator float merrily downstream, in different time frames, probably from different starting points, certainly oblivious to each other's progress. Yet, you can be quietly confident that you're on tributaries of the same river with one ultimate destination.

Our third picture highlight all possible key cards for various starting cards. More than half of the packet doesn't even get a look in.


Of course, had the original array been as above but with the 5 and 4 of Diamonds switched, then all roads would have lead to the very end.

Why does it work?

Here is a heuristic argument----modified from one suggested by Tony Phillips of SUNY, Stony Brook, for a full deck---which sheds some light on the phenomenon.

There is a 1/6 chance of you picking the same first card as the spectator.

On average, that first card has value (1 + 2 + . . . + 6)/6 = 21/6 = 7/2.

That's also the average length of subsequent steps, so the density of the spectator's key cards can be expected to be 2/7.

Similarly, you yourself should encounter about 6 key cards on average after the first, since (24 - 3.5)/3.5 = 5.86. Each of these has a 2/7 chance of being one of the spectator's key cards, and hence a 5/7 chance of missing.

The probability of you {\em not} hitting one of the spectator's key cards on the first or any later chance is therefore (5/6) x (5/7)6 = 0.11.

So, the probability of a win for you, by this rough estimate, is about 89%, which is not shabby.

A full mathematical treatment of these ideas can be found in the paper "On Kruskal's Principle" by Wayne Haga & Sinai Robins, who also provide a great online simulation.

One presentational option is to write down an actual prediction, which is left to one side, right before you hand the spectator the packet of 24 cards to deal. At the end, you can then turn back and say, "Earlier I wrote down the card I thought you'd get to." The spectator's card is now turned face up, and is found to match your written prediction.

Magician Gordon Bean, in his article "A Labyrinth in a Labyrinth" from Puzzlers' Tribute (AK Peters, 2002), suggests spelling out one card for the each letter in the name of the value of key cards, so that, for instance, "ten" advances only three cards (T-E-N). This greatly increases the likelihood of reaching the same sticking point. A word of caution, however: spelling values on this scale is risky, as it's so easy for one or both of you to get confused and revert to ordinary counting.

Run through a full demonstration of whichever counting procedure you adopt, pausing at each key card for clarity, before you let the spectator loose with the cards. It takes patience and care on the part of two people for this to work out.

The Final Word(s)

Linguistic applications of the Kruskal count principle, leading to a final key word in a piece of text, are entertaining in their own right, and were much loved by Martin Gardner. Author John Allen Paulos, winner of 2013 Joint Policy Board for Mathematics (JPBM) Communications Award, has a nice treatment of a Kruskal-inspired biblical hoax in his book Once Upon a Number--The Hidden Mathematical Logic of Stories (Basic Books, 1998). The excerpt in question is freely available online.

(On an tangentially related note, readers may be interested in a miracle of bibilical proportions—related to card magic—which we recently wrote about elsewhere.)

Finally, a word about Persi Diaconis & Ron Graham, whose wonderful writing on de Bruijn sequence card magic we've referenced here in December 2008, and December 2011. Their beautiful and inspirational book Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks (Princeton University Press, 2011) is winner of the 2013 Euler Book Prize.

'Tis a season of celebration!

Curiously, "Outranks Luck" is an anagram of "Kruskal Count." 

Wednesday, October 31, 2012

All or Nothing Trickle Treat

Just in time for election season, we present a ternary trickle down principle. First, we note that Martin Gardner (1914-2010), the best friend mathematics ever had, would have turned 98 on 21 October. There is a Twitter feed in his honor at WWMGT, for which suggested contributions (What Would Martin Gardner Tweet?) are welcome. 

In the USA, Gardner did for recreational mathematics what Julia Child did for recreational cooking. His influence spread much further afield actually, and like Child, he also inspired quite a few professionals along the way: mathematician and card expert Persi Diaconis has correctly noted, "he has turned thousands of children into mathematicians," playfully adding, "and thousands of mathematicians into children." After the above culinary comparison was made, author and Gardner friend Chris Morgan commented, "I was lucky to have spent time with Julia in the 1980s (I took three cooking classes with her in Boston). She was very much like Martin in many ways." 

Last October here, we made available here numerous card classics that Martin had published in his legendary "Mathematical Games" columns in Scientific American, following up on the earlier June 2010 and August 2010 Card Colms

October is now well established worldwide as the anchor month for annual Celebration of Mind events, which promote Martin's wide interests and remarkable and extensive written legacy. These gatherings bring together young and old, trained and untrained, to have fun with logic, puzzles, magic, optical illusions and more, very much in the spirit of the ever-curious Gardner. 

This year, in addition to seventy plus Celebration of Mind events listed at the event map here, there are an equal number of Flexagon Parties going on all over the globe, inspired by Vi Hart's viral videos on YouTube (don't miss the fourth food themed one, which would have delighted both Child and Gardner). Vi was of course inspired by the Hexaflexagons article which marked the start of Gardner's quarter century tenure atScientific American

Incidentally, it's not too late to host or attend events of either type. For instance, this year's MAA Celebration of Mind event is set for 5th December. Please consider joining or hosting an event, formal or informal, wherever you are. 

October is also when the world's most extensive and successful mathematics outreach programme Maths Week Ireland is held. This year, over a nine day period ending on Martin's birthday, it exposed over 150,000 people of various ages in both the Republic of Ireland and Northern Ireland to the joys of mathematics and logical thinking, with several nods to Gardner thrown in for good measure. The closing event was really a Celebration of Mind show and tell for the whole family, facilitated by a dozen presenters, which over a thousand people attended. I had the pleasure of participating, sometimes alongside notable Gathering for Gardner regulars such as Fernando Blasco. Top notch speakers included Colin Wright and David Singmaster. 

It was while driving towards Sligo a fortnight ago with Maths Week Ireland mainstay Dr. Maths, on the way to address hundreds of school children, that I was introduced to a delightful recreation with triangles which forms the basis for this month's offering here. Like the title below, it's hard to resist, and I'm confident that Martin would have found it fascinating.


Humble Contribution

Start with a row of n items randomly selected from three possible types, say red, blue and white poker chips. Underneath each pair in the row, place a third item to form triangles, according to this rule: 


If the two vertices above are the same colour, then the third one matches both, whereas if the two vertices above are different colours, then the third one is different from either. 

In other words, in each such downward-pointing tiny triangle, one never has only two vertices matching. When it comes to vertex matching, it's an all or nothing situation. 

Once the initial row of n items is processed to yield a second row of n - 1 items below it, process that row in the same way, to get a third row of n - 2 items underneath it. Continue, eventually getting a single item at the very bottom of an n-row triangle. 

Here are three examples with poker chips: 


Note that in each three-chip downward-pointing trianglebut not necessarily in their upward-pointing cousinsany two vertices determine the third according to the All or Nothing rule. Hence, upon reflection, or should we say upon rotation, any completed triangle (of any size) may be turned 120 degrees in either direction to yield an equally valid arrangement. Indeed, the second and third images above are exactly such rotations of the first one! 

Here is the main question we wish to ponder: 



Given the top row of such a triangle, of any size, can one easily predict what the final bottom vertex will be?

Note the pleasing random-seeming arrangements of "solid sub-triangles" of various sizes in red, blue and white, which make up the larger triangles above. It almost suggests a fractal behaviour. 

This can all be implemented with cards, for instance, using only three suits (which coincidentally was considered in the last Card Colm). 

Alternatively, we could use face-up red and black and face-down cards for the three types, as illustrated below. 





The secret here is to focus on the fourth row from the bottom: specifically its starting and finishing items. Those two cards alone determine the final bottom card according to the All or Nothing rule! No matter what other two cards are between the face-down blue-backed card and the 7 of Hearts, the final card will always be Black. In fact for every downward pointing "four triangle," consisting of ten cards, any two of the three vertex cards determine the third according to the same rule. 

What's so special about four? Here's a hint: it's also true for downward pointing "ten triangles" consisting of 45 cards headed by a row of ten cards. Here's a perfectly reasonable question to also ponder: what is the next number after ten which also works? (You'll need eight decks of cards.) 

Now suppose the following five cards are laid out, and our goal it to speedily guess the nature of the last card if the associated fifteen card triangle is completed. 


It's easy to see that the first card in the next row should be Black. Likewise the last card in this row should be Black, so the final card of the completed triangle should also be Black. 

A similar "trickle down" approach can be used to predict the nature of the final card starting with rows of length six or seven. For longer rows, it may be easier to go the other direction, noting that, 

Given a triangle of any size, it can be extended upwards in exactly 3 distinct ways, by first deciding on the nature of any single card in the row above, and then filling in the rest to be consistent with the All or Nothing rule. Just be sure to always "trickle down" (not up)!

It's not hard to do this for a row of nine cards, extending it mentally to a row of ten and then quickly deducing the nature of the final card at the bottom if eight more rows were constructed. 

The principle underlying the above observations may be found in the upcoming paper "Triangle Mysteries" by Erhard Behrends & Steve Humble, which is due to appear in The Mathematical Intelligencer in June 2013. There, the result hinted at above is generalized, and the connection with Pascal's triangle is explored in depth. Thanks to Steve (Dr. Maths) for the preview! 

Note that from a large downward-pointing trianglewhich is as we noted completely determined by any of its three sidesone can also carve out Halloween hexagons with interesting properties. Have fun! 

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. 

Thursday, June 28, 2012

Something Old, Something True, Something Borrowed, Something New


Something Old

There's an old scam in which a victim is offered a free choice of any five of ten face-down cards, to serve as a poker hand, the other five being retained by the person offering the cards. When the resulting poker hands are compared, it turns out that the victim has the losing hand. 

This can be repeated as often as is wished. This principle, often referred to as the "Ten Card Poker Deal," goes back at least as far as Card Control (2nd ed., 1947) by Arthur Buckley. 

Another version sees the victim being permitted to win a few times at first, in order to instill a false sense of confidence, perhaps before the game is played for money. Then, the winds of fortune mysteriously change. 

For one performance only, the cards could be offered openly, face up, one at a time. A high-valued card such as Ace is an early contender for attention, it being assumed that the victim won't be able to resist its fatal charms. 

The secret is very simple. As hinted at above, there is a single dud among the ten cards---in isolation it may appear to be valuable---such that whoever gets it loses without a doubt. The other nine cards are carefully planned in advance of course, but the person offering the card choices just has to make sure that the victim gets stuck with the dud. 

We've been deliberately vague about how the cards are offered to the victim and then selected; various methods can be used. Perhaps the dud's back is subtly marked, so that it can easily be tracked, and steps are taken to unload it ASAP. 

Such not-so-honest approaches are far from the spirit of mathemagical effects, so in what follows we instead offer three ingenious and fair-seeming ways to arrive at the desired card distribution. These methods have been explored in previous Card Colms, and can be used here to control who wins on each round. 

The required ten cards are: three sets of three of a kind, for instance three 3s, three 8s, and three Kings, together with the dud, which is any non-matching card---below we'll settle for a Jack---which is known as the Jonah card. Whoever gets the Jonah card loses, without fail. 

The suits here can be arbitrary; for that matter the relative values play no role either, as they are never compared.


Something True

Before we show why success or failure here always boils down to control of the Jonah card, we need to be clear as to the ranking of the various possible poker hands, i.e., selections of five cards from a standard deck. 

There are 52!/(5!47!), or roughly 2.6 million such selections, which is so many that even if you were to play enough poker in your life to encounter 100,000 hands, you'd still only have seen less than 5% of them. 

The relative scarcity (and hence value) of some of the commonly desired Poker hands is reflected in this chain, starting with the rarer hands: 




Royal flush > straight flush > four of a kind> full house >
flush> straight > three of a kind > two pairs > one pair.


The rankings are transitive, so that for instance, a flush beats two pairs, but four of a kind beats both. 

Returning to the Jonah card issues, let's suppose that the cards in question are: 3♣, 3♠, 3♦, 8♥, 8♣, 8♦, K♥, K♠, K♦ and J♠. 

First focus on the hand with the Jonah card; it's not difficult to see that one of the following three cases must hold. 

Case 1: This hand also contains three of a kind, and one other card, as shown in the top row here. The bottom row is the other hand. 

    

    

Figure 1: Typical losing and winning hands in Case 1


Then the other hand wins, being a full house containing three of a kind and a matching pair. There are 54,912 five-card hands with just three of a kind, compared to only 3744 full houses. The hands are something like what is shown above. 

Case 2: The hand with the Jonah card also contains two pairs, as shown in the top row here. The bottom row is the other hand. 

    

    

Figure 2: Typical losing and winning hands in Case 2


Then the other hand still wins, containing three of a kind and two unmatched cards. There are 123,552 hands with two pairs, compared to only 54912 hands with just three of a kind. The hands look something like what is shown above. 

Case 3: The hand with the Jonah card also contains one pair and two non-matching cards, as shown in the top row here. The bottom row is the other hand. 

    

    

Figure 3: Typical losing and winning hands in Case 3


Then the other hand wins one more time, as it contains two pairs. There are 1,098,240 hands with just one pair, compared to 123,552 hands with two pairs. The two hands look something like those above. 

In conclusion: the trick, so to speak, is to control who gets the Jonah card.

Something Borrowed

Here are three clever ways to control who gets the Jonah card, while appearing to randomise how the cards are distributed.
  1. In the April 2006 Card Colm, we explained Bill Simon's 64 Principle in general, and two months later applied it to the control of ten cards for two poker hands in Better Poker Hands Guaranteed, specifically in "Better Poker Hands with Bill Simon." The probabilistic considerations there can be ignored however; we know what we're dealing with here, and there's only one card to control.
  2. It was also in the June 2006 Card Colm, that we introduced a Position Parity method of controlling card distribution for two poker hands, in "Martin Gardner's Coins to Cards Effect," and "Better Poker Hands with Martin Gardner."
  3. In the October 2008 Card Colm, we explored the Monge Shuffle, which is an in-hand way to mix cards.

    As seen in "Better Poker Hands With Gaspard Monge" there, it's especially interesting for a packet of ten cards, because the cards in positions two, five and eight just keep cycling around, and the one in position four doesn't move at all. So the ten cards can be subjected to as many Monges as the victim asks for, and assuming the Jonah card started in one of the four key positions just mentioned, it's still in one of those slots. The losing hand can be teased out using a spelling routine as suggested in that 2008 column, but a much easier option is available.
Something New
  1. When using Bill Simon's 64 Principle, simply start with the Jonah card in any of positions three to six from the top of the packet of ten cards. Plenty of innocent-looking in-hand shuffling can be done which preserves that key fact, before launching into the "free-choice" phase.
  2. To implement the Position Parity method, pay attention to which end of the row of ten the selections start from, and who picks first. That way, you control everything just by knowing if the Jonah card starts in an even- or odd-numbered position. Additional shuffling of various types can be done which won't change the outcome, for instance, experiment with running off---into a waiting hand---either an even or odd number of cards, and putting them back at the face or behind the remainder. (Start with alternating Black and Red cards to get a feel for the possibilities.)
  3. It's easiest of all to Monge Shuffle repeatedly: arrange it so that the Jonah card is in the position four at the outset. It stays there throughout any number of Monges, so that when the victim is satisfied that the cards are mixed, you can either say, "You take the top five, I'll take the rest, let's see how we did," or deal into two piles, alternating, making sure the victim gets the second one. You could even add more layer of deception in the dealing situation; asking for one of the piles to be indicated, saying, ``You want me to have that pile? Fine," if it's the first one, and "That's the pile you want? Okay," if it's the second one.

Monday, April 30, 2012

Splitting the Pot


Dedicated to the memory of Thomas M. Rodgers (1944-2012)


In the February 2012 Card ColmAmazon Arrays (Large Action), we considered 4 by 4 arrays such as, 
Each row (and each column) contains each suit once, and each row (and each column) contains each of the four values Jack, Queen, King & Ace once. Hence we have an example of an orthogonal (or Graeco) Latin square, which can be dealt from a packet of sixteen cards in four columns and rows from left to right. 

Gather these cards together, shuffle, and again deal face-up left to right into four rows and columns. (Overlap a bit vertically, to facilitate later top-to-bottom gathering by columns.) It's likely to end up with an array such as the following, devoid of the special characteristics of the last one.



Yet, some structure remains. Can you see what it is? 


No matter how the cards are dealt, it's possible to pick out one from the first column,
another from the second, a third from the next one and a final one from the fourth,
so that overall we have selected one Jack, Queen, King and Ace, in some order.

The same now holds for the remaining columns of three cards on the table, and the columns of two cards that result when those four cards are removed, and so on until we have just one card of each value remaining, in a single left-to-right row. It's instructive to confirm these claims, one by one, for the array above. To understand why it's all true, perhaps work up from 2 by 4 arrays of two Jacks, Queens, Kings and Aces, to 4 by 4 arrays of four of each. 

The highlighted claim above is equivalent to saying that it's possible to reorder the cards within each column, so that each resulting row contains one card of each value. 

We are not claiming that the first Jack in the last row above can be replaced by a King above it; that would be too much to ask for. However, the second Jack in the last row can be replaced by the King three cards above it, so all is well. 


The highlighted claim above is equivalent to saying that it's possible to reorder the cards within each column, so that each resulting row contains one card of each value. Here is the result of four column reorderingsamong several possible ones for each column-for the last 4 by 4 array. It utilizes the switch just suggested:
Of course everything just claimed about random arrangements of these sixteen cards holds true if the words "row" and "column" are interchanged throughout, or if we focus of the four suits rather than the four card values in question. 

However, as we move forward, we concentrate on the occurrences of distinct card values from left to right, across columns, there being corresponding observations for suits from top to bottom, across rows. 

Is this all a special property of square arrays? To find out, let's pick up the cards, throw in the four 10s too, shuffle the resulting packet of size twenty, and deal out left to right into five face-up columns of four cards. Something like this will be seen: 
Once again, some structure is evident. As above, it's possible to pick out one card from each row, to that overall we have one of each suit. Also, extending what we had above, 



No matter how the cards are dealt, it's possible to pick out one from each column ,
so that overall we have selected one 10, Jack, Queen, King and Ace, in some order.

The same now holds for the remaining columns of three cards on the table, and the columns of two cards that result when those four cards are removed, and so on. It's worth confirming these claims for the array above. 

Of course, it's all equivalent to saying that it's possible to reorder the cards within each column, so that each resulting row contains one card of each value. Can you perform five such column reorderings for the last 5 by 4 array? 

Let's not stop there. Shuffle the entire deck, and deal into thirteen columns of four cards. It should not come as a surprise that no matter how the cards are dealt, it's possible to pick out one from each column so that overall we have selected one 2, 3, 4, ..., 10, Jack, Queen, King and Ace, in some order. It's also possible to pick one card from each row to end up with one of each suit. Similar observations apply to the scaled-down arrays resulting as the desired sets of card are removed. 


So, what's going on? Colin Wright kindly alerted us to a tie in with Philip Hall's Marriage Theorem. David Leep & Gerry Myerson consider this application in their 1999 American Mathematical Monthly paper Marriage, Magic & Solitaire. Most of the proof can also be found online on page 7 of Notes on Matching by Jonathan Hirata. 

Can you find a more elementary (or direct) proof in the case of n by m arrays of cards as considered above?


Deal/Ply/Finagle, Live

Ask for four poker players to step forward. Hand the 10s, Jacks, Queens, Kings and Aces to the first of them, and have that packet of cards shuffled and dealt into five overlapping face-up columns of four cards each. Comment briefly on the arrangement that results, and quickly pick up the columns one by one, gathering from top to bottom, shuffling each in hand before dropping it in a face-down pile. Gather the piles in any order, perhaps asking others for input along the way. 

Hand the packet back to the first player and have it dealt again, but this time into four overlapping face-down columns of five cards each. Pick up one of the columns and hand it to the player, saying, "These cards are destined for you. Please don't look at them yet." 

Gather up the remaining fifteen cards and hand them to the second player to shuffle and deal into five overlapping face-up columns of three cards each. Again comment on the arrangement that results, and quickly pick up the columns one by one, gathering from top to bottom, shuffling each in hand before dropping it in a face-down pile. Gather the piles as before. 

Hand the packet back to the second player to deal into three overlapping face-down columns of five cards each. Pick up one of the columns and hand it to the second player, saying, "These cards are destined for you. We'll look at them later." 

Gather up the remaining ten cards and hand them to the third player to shuffle and deal into five overlapping face-up columns of two cards each. Quickly pick up the columns one by one, gathering from top to bottom, shuffling each in hand before dropping it in a face-down pile. Gather the piles as before. 

Hand the packet to the fourth player, saying "Let's get you involved too," and have it dealt into two overlapping face-down columns of five cards each. Say, "There are two poker hands here, you get to pick which one you want." The other one is then given to the third poker player. 

Stress the randomness of all than has taken place, the repeated shuffling, the fact that the cards were out of your hands, and so on. The last point is not entirely true of course, but you can point out that you shuffled the piles as you gathered them, and others decided in what order they were collected. 

Have the four poker players inspect their cards. They should all have straights: a 10, Jack, Queen, King and Ace, with the suits jumbled randomly. End with some congratulations, and "I guess you'd split the pot if this was a real game." 

Should one or more person happen to have straights in just one suit, this is extra reason for celebration; act like it was entirely expected. 

How can such order be wrestled from chaos? There are two secrets here: your knowledge of the principle discussed earlier, and some hitherto unmentioned details as to exactly how you shuffle those columns as you gather them up! 

Let's suppose that the initial display of cards is the one seen earlier above: 


Quickly scan horizontally, seeking a complete row, namely one of each of the five values, or a relatively complete row, such as the third row above, or maybe just focus on the last row, which has three Queens here. There are three possibilities to consider. 

If a complete row is spotted, say the second one, then gather up the columns in any order, and after the cards are dealt again, face down, have the second column of five cards given to the first player as a poker hand. 

If a relatively complete row such as the third one above catched your attention, then conspire to have the Queen at the bottom of the third column there switched with the King above it as the columns are gathered up; which results in the third column of five cards dealt being a suitable poker hand for the first player. 

Perhaps a more convincing approach, however, is to focus on the final row: if the Queens at the bottom of the second and third rows could respectively be switched for either of the 10s or Kings above them all would be well, allowing for gathering in any order and dealing and finally setting aside the last resulting column of five cards as the poker hand for the first player. The same effect can be achieved as follows: gather up the first column and do some casual in-hand shuffling of these four cards, discretely peeking at the bottom and only stopping when the Ace is back there. Place the cards face down in a pile on the table, and repeat for the second column, this time shuffling until either of the two 10s are spotted at the bottom. For the third column it's a King that needs to end up on the bottom. For the last two columns, either the card already at the bottom, or a card of the same value, needs to end up there. In any event, it's the final column of five cards dealt that forms a suitable poker hand. 

Of course the poker players don't know where this is going, and hence don't know what to look out for, so you can probably get away with it. The same strategy is applied in later rounds. The frequent shuffling by the players, and the random order in which the piles are collected by you, seems to add to the fairness, but neither has the slightest impact on the outcome. 

Curiously, "A Gatherer Memoir" is an anagram of "Marriage Theorem." Two decades ago, Thomas M. Rodgers was the original gatherer for Gardner; of fans of mathematics, magic, puzzles and more. The Gathering for Gardner conferences he helped to start have grown into tremendously stimulating, innovative, and wide-ranging affairs, bringing together creative like-minded souls in the arts, mathematics and related fields. 

The Gathering for Gardner offshoot concept, Celebration of Mind, another product of Tom's vision and energy, with even more potential to make an impact far into the future, takes place worldwide every October. These events are free and open to all. Please participate by either attending or hosting one yourself! 

Thanks to Colin Wright for the initial inspiration this month. 

"Deal/Ply/Finagle, Live" is an anagram of "A Level Playing Field." 

Wednesday, February 29, 2012

Amazon Arrays (Large Action)

Consider the following 4 by 4 array, which is one solution to an old challenge revived in Jim Wilder's fun blog.

   
   
   
   


Such "orthogonal Latin squares" have a long history, going back at least as far as Jacques Ozanam in 1725, and were again considered by magician Jean Hugard fifty years ago.

The above array can be dealt from a suitable packet of sixteen cards in four rows from left to right, where we suggest that the cards in each column overlap a little to facilitate subsequent gathering by columns.

Actually this array was derived from the solution which Jim Wilder gave (linked from his blog) by repeated application of these steps: gather up each column of that array, from top to bottom, and re-assemble the packet by collecting the columns in any order, and deal again from left to right, then once more collect the columns in any order, and so on.

Further applications of this type of mixing yields the array below:


   
   
   
   


This shares two crucial properties with the first array above and the one at Wilder's link: Each row (and each column) contains each suit once, and each row (and each column) contains each of the four values J, Q, K, A once.

Natural questions arise, which we leave interested readers to ponder:
  1. Are these properties preserved under all such mixing, independently of the order in which the columns are collected? (Note that collecting the columns in left to right order and dealing left to right again is equivalent to matrix transposition across the diagonal).
  2. What characterises arrays of four cards of each suit so that they have the desired two properties? How can we construct one? (The September/October 1961 issue of Hugard's MAGIC Monthly has a nice answer to the last question on page 11).
  3. How many different arrays of four cards of each suit are there having the desired two properties? (Say, up to reflection and rotation?)
  4. Can each possible array be obtained from any other one, such as the first one above, by repeatedly collecting columns in some order and dealing over?
  5. Are other "four representatives" properties preserved, involving say the middle four cards or the four corners? Or the main diagonals? If not, would they be if we restricted the allowable permutations of the columns pickup to those of even sign?


Tragic Alone

Instead of dealing cards face up and using notable values such as J, Q, K and A as above, one could deal face down and use other innocuous values, for instance: 2, 3, 5, 8.

Start with an appropriate face-down array, perhaps dealt from the top of a supposedly shuffled deck--mix the rest of the cards all you want while maintaining the top stock. Have the sixteen key cards mixed further by collecting columns and dealing out again as above. Ask a spectator to point at any card, then place a small object such as a glass over it. Have the other three cards in the row (or column) containing the special card pulled to one side, then have them plunged one by one into the rest of the deck. Shuffle again, and then let these thirty-nine cards drop to your side in one hand, and request that the twelve remaining cards on the table (not counting the special one) be gathered up and given to you. Shuffle those in as well, and finally announce that with a quick scan of the card faces you will determine which card is missing.

Turn around so nobody can see as you fan the cards. You promptly name the card under the glass. The deck can be handed out for inspection; all the evidence of what went on is gone.

All you need to know is the three values and three suits represented among the three other cards in the row (or column) containing the special card. When you offer the deck to have those three cards plunged in, have it face up but with a face-down card at that end to hide that fact. Flip it back over before the other twelve cards are inserted. At the end, you run through the "face-down" deck to locate the three face-up cards, which will reveal all. Finally flip them over again match the orientation of the rest of the cards, before you turn around and announce what the hidden card is.

Alternatively, you may wish to skip all the subterfuge and simply ask to see the other three cards in the row (or column) containing the special card; however in this case, gather up the other twelve cards in the array and shuffle them into the rest of the deck, before anyone has a chance to note that only four values are being used.

Genial Actor

The card values 2, 3, 5, 8 have another special property explored in Additional Certainties, the February 2008 Card Colm, and Two Summer Difference Certainties, the June 2009 Card Colm. Namely, if two of them are selected and their sum is reported to you, then you know what both of them are. Can this be exploited in conjunction with the earlier ideas above?

Certain Goal

The arrays considered throughout are of course magic squares, and as such can be employed in the usual prediction and forcing stunts, e.g., see Quasi-Masked Forcing Kind of Magic Squares, the February 2007 Card Colm.

"Amazon" is an anagram of "Ozanam;" whereas "Large Action," "Tragic Alone," "Genial Actor," and "Certain Goal," are all anagrams of "Graeco Latin".

Thanks to Jim Wilder for the initial inspiration, and also to Alexander Bogomolny of Cut-the-Knot for helpful input.

Colm Mulcahy (colm@spelman.edu) completed his PhD at Cornell in 1985, under Alex F.T.W. Rosenberg. He has been in the department of mathematics at Spelman College since 1988, and writing Card Colms—the only MAA columns to actively encourage lying on a regular basis—bi-monthly since October 2004. For more on mathematical card tricks, including a guide to topics explored in previous Card Colms, see http://www.spelman.edu/~colm/cards.html.

Follow Card Colm on Twitter at @CardColm