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."
I was enchanted with Kruskal's Principle when it appeared in MG. I ran some computer simulations and shared the trick with my students. For me, the operative clause in the MG article was:
ReplyDelete"Once this happens, the chains will be identical from that point on."
I visualize the deck state as a graph, where the terminus is an attractor. The majority of the chains lead to it as the root of a subtree of the graph.