The card effect below is based on a clever probability-defying principle involving permutation cycle decomposition, which was learned from a boxes and prisoners puzzle popularized by Pete Winkler of Dartmouth College. Appropriately enough, Pete introduced it at Gathering 4 Gardner 7 in Atlanta in 2006. Much of what follows below grew out of discussions with Dan Kalman of American University; indeed it was Dan's idea to migrate this lovely puzzle to the card setting.
Inexact Iffy Verso
Twelve cards from a borrowed deck of cards are jumbled by an audience member, who then deals them into a neat face-up three by four array—something like what is shown here—while you avert your eyes for a while so that you do not see any card faces. Any Ace to Queen in mixed suits are used, but don't draw attention to that. Do emphasize that the cards were borrowed and mixed, so that there is no chance of marked cards being used.
Have any four cards of different suits singled out, and their names written down on a sheet of paper which is then folded over, before the cards are all turned face down. For the sake of argument, let's suppose 4H, JS, 2C, are 8D are the chosen ones. Finally, you turn back to face your audience.
"These twelve cards from a borrowed deck have been randomized," you say, adding, "Only those of you who viewed them before they were turned face down know where anything is. I'd like to introduce you to four special friends of mine, who have a knack for finding things on demand. Actually they have x-ray vision." Four people enter the room. In reality, they are accomplices of yours who've agreed in advance on a mathematical strategy for locating any cards they are asked to.
Continue, "If one of my friends were to look for the Heart written on the sheet, and we allowed her to peek at up to nine of the twelve cards, she'd have a 75% chance of finding it. If a second of my friends did the same thing for the Spade on the list, and he hadn't seen the outcome of the first search—let's assume the cards always start off in the same neat array—that would be an independent event. Hence, the chance that both of my friends would succeed would be 3/4 squared, which is only about 56%. My other two friends seek the remaining two cards noted—the Club and Diamond—in the same way. For all four to succeed would be even less likely, since 3/4 to the power of four is only about 32%. Yet, that's exactly what I think will happen, about three quarters of the time.''
Pause to let that sink in, before summarizing, "Yes, I'm saying that if four people independently do something with a 75% chance of success, all four will succeed almost 75% of the times. We're re-writing the rules of probability here. The secret is simple: They're really using their x-ray vision to gradually steer them to the correct cards. It's not perfect, but it's much more impressive that leaving things up to mere chance."
One of your friends steps forward, you introduce her and add that she's very good at finding specific Hearts via x-ray vision. The rest of your friends turn away. Stress that none of the four gets to see the results of anyone else's peeking.
The audience member looks at the sheet, and shows your friend the Heart on the list, the 4H. Your first friend peeks at up to nine cards in the array, stopping as soon as she finds the 4H. If she fails, you admit defeat and start all over, having the cards re-shuffled and re-dealt. If she succeeds, have your second friend shown the Spade on the list, and continue if he too succeeds in finding his target card. If your friends all peeked at random, then as explained above, the chance they'd all succeed would be only 32%. Here's the big surprise:
of your friends succeed about 73% of the time, on average.
Here is the strategy, explained in terms of the specific card array above. It is indeed the result of a kind of x-ray vision: a mathematically-enhanced vision which allows those in possession of this superpower to "see through" an array of card backs and locate a desired card more easily than seems reasonable.
First, let's agree to associate each position in a three by four array with a specific number 1-12. We suggest an easy-to-remember but not too obvious assignment such as this "reverse-Z":
05 06 07 08
12 11 10 09
The values of the cards which end up in those positions can be thought of as a permutation of the numbers 1 to 12. The array shown earlier is reproduced here for convenience. In practice, the cards are all face down. It's all about the card positions and values, suits play no role at all; the earlier fussing about selecting a card of each suit to locate is just a distraction from what's really going on. The "reverse-Z" convention, however, serves a real purpose: it should make it less likely for spectators to catch on to the peeking strategy soon to be explained.
The first person—who hopes to locate the 4H—starts by peeking at the 4th card according to the above convention, namely, the 6H. That suggests that for her second try she peeks at the 6th card on display, which is the QH. That in turn points to the 12th card for her third try, which is the 9H. For her fourth try she peeks at the 9th card, which is the 3D, then for her fifth try she peeks the 3rd card, which is the 2C, then for her sixth try she peeks at the 2nd card, which is the 7H. Her seventh try is the 7th card on display, which is the desired 4H. She has succeeded within nine tries.
The cards are restored to a neat face-down array and the second person now views the scene, having not witnessed the first person's peeks. He hopes to locate the JC, and hence starts by peeking at the 11th card, which in the above convention is the 10C. That suggests that for his second try he next peek at the 10th card on display, which is the AD. That points to the 1st card for her third try, which is the desired JC. He too has succeeded, as hoped for.
The third person hopes to locate the 2C, and starts by peeking at the 2nd card, which is the 7H. It can be checked that if the procedure outlined above is followed, the 2C is arrived at on the seventh peek. The fourth person hopes to locate the 8D, and starts by peeking at the 8th card, which is the 5S. The 5th card is the 8D, so the target card is arrived at on the second peek.
For the specific array depicted above, we can therefore say:
by starting with a peek at the card at the position corresponding
to the target card's value, and then "following the trail."
Does it always work, within nine tries? Definitely not! But it works more often than not. The display above corresponds to the permutation that sends 1, 2, 3, ..., 12, to 11, 7, 2, 6, 8, 12, 4, 5, 3, 1, 10, 9, respectively. It can be checked that its cycle decomposition is (1 11 10) (2 7 4 6 12 9 3) (5 8): a product of a 3-cycle, a 7-cycle and a 2-cycle (the last being a transposition or inversion). Here 3 + 7 + 2 = 12, and there is a natural connection with the numbers of tries the four people needed above: 7, 3, 7, and 2, when seeking cards of values 4, 11, 2 and 8, respectively. The 4H and 2C are in the 7-cycle, the JS is in the 3-cycle, and the 8D is in the transposition. For this array, all twelve cards are findable within seven peeks, the AD and 10C only need three peeks, and the 5S only needs two. Moreover, had the 5S and 8D above been switched, each would have been discovered on the first peek, as the cycle decomposition would then have been (1 11 10) (2 7 4 6 12 9 3) (5) (8).
What can go wrong? Consider the next array, which only differs from the one depicted above by having the 9H and 10C switched.
This new display corresponds to the permutation that sends 1, 2, 3, ..., 12, to 11, 7, 2, 6, 8, 12, 4, 5, 3, 1, 9, 10, respectively. Its cycle decomposition turns out to be (1 11 9 3 2 7 4 6 12 10) (5 8): a product of a 10-cycle and a transposition. Hence ten of these cards, specifically the AD, JS, 9H, ..., 10C, will require ten peeks to locate using the suggested strategy.
The moral is that some arrays, namely those avoiding cycles of length greater than nine, will guarantee 100% success, whereas others will lead to certain failure. The question then arises, how many (or what fraction) are there of each type?
On page 3 of Pete Winkler's "Seven Puzzles You Think You Must Not Have Heard Correctly," a simple counting argument is given to show that the probability of a uniformly random permutation of 1-12 having a k-cycle (for k > 6) in its cycle decomposition is 1/k. Having such a long cycle rules out the possibility of having another, since the cycle lengths sum to 12. Hence, it follows that the probability of a random permutation of 1-12 having a 10-cycle, 11-cycle or 12-cycle is 1/10 + 1/11 + 1/12, which is roughly 0.2742. Thus, we can assert:
of different values from a random array of 1-12, within nine tries,
using the suggested strategy, is 1 - 1/10 - 1/11 - 1/12, or about 73%.
It's even more impressive if more than four people are involved, since it beats the odds more convincingly, but it's also too time consuming. The "one of each suit" approach taken above is just an attempt to keep audience interest up for four rounds of peeking.
Secondly, It's As Easy As ABC
We now suggest an improvement on the above: a similar effect which can be pulled off with 100% certainty, but allowing fewer peeks. The probability of any number of people all finding their pre-assigned cards of different values from a random array of 1-12, within six tries, using the suggested strategy, goes down to 1 - 1/7 - 1/8 - 1/9 - 1/10 - 1/11 - 1/12, or about 35%. This is the setting of the problem adapted from Pete Winkler; allowing only half of the cards to be peeked at. It's remarkable that the probability of success is so much higher than the chances of four people finding all of their cards by just peeking randomly, which is (1/2)^4, or about 6%.
A way to ensure success every time for your four friends is to control the cycle structure of the initial array permutation. For instance, with only six peeks permitted, it would help if we could somehow arrange that there be a 6-cycle, as then there couldn't also be a longer one. To do this we need to change the rules a bit, and be able to think very fast on our feet.
Above we saw how a single switch of two cards turned a 7-cycle and a 3-cycle into an undesirable 10-cycle. The very same kind of switch can be used to break up a long cycle into two more desirable shorter ones. So suppose we proceed as before, throwing in a comment such as, "Mix the cards all you want, and deal them into a three by four grid, face up. Switch pairs of cards over and over to make sure they're really mixed up. Then I'll do one more switch for good luck." This time around, you get to see the card faces of course.
If your last switch is done with great care, the final array will not have any cycles longer than six, and total success will follow. It's important to do this before you have the four target cards written down, to allay suspicions that your switch is related to those selections. Nevertheless, human psychology being what it is, it's likely that the cards you switch will not be chosen as two of the four to be found! People will also worry here that you are somehow communicating information gleaned from your viewing the cards to your friends; this is not so, once the cards are all turned face down the four target cards are located solely on the basis of the peeks.
Here's an example. Suppose that the audience member mixes the twelve cards and deals them into a three by four array, then does several card switches, leading to this display:
This display corresponds to the permutation that sends 1, 2, 3, ..., 12, to 5, 8, 12, 11, 1, 9, 6, 2, 7, 3, 4, 10, which has cycle decomposition (1 5) (2 8) (3 12 10) (4 11) (6 9 7). This needs no adjustment—every card is findable within three peeks—but for the sake of consistency, switch any two cards within any of the five cycles shown; it's still guaranteed to lead to success.
Here's another example. Suppose that this is what you are faced with:
This corresponds to the permutation that sends 1, 2, 3, ..., 12, to 7, 12, 1, 4, 6, 8, 3, 11, 5, 2, 10, 9, which has cycle decomposition (1 7 3) (2 12 9 5 6 8 11 10) (4). This has an 8-cycle, which we now consider undesirable. Switching the final 10C with the midstream 5S turns out to break up the 8-cycle into the two 4-cycles (2 12 9 10) and (5 6 8 11).
Can something like this be done in general? Namely, the detection and breaking up of a too-long cycle? Yes, here's a better way than that done above, courtesy of Dan Kalman, which avoids working out the full cycle decomposition first. Mentally follow the cycle from the AD until it either ends or goes past a sixth card. If the latter, swap the seventh card in the cycle with the Ace. If, on the other hand, the Ace-generated cycle ends too early, mentally follow the cycle from the 2C (or the lowest-valued one that was not in the first cycle), and this time, if you reach a seventh card, simply switch it with the 2C. This forces a 6-cycle, so that as mentioned above, it doesn't matter what the rest of the cycle structure is.
If there is a too-long cycle in the initial arrangement, the chances of finding it in one or two tries as just suggested is high. Otherwise, i.e., if you don't find any long cycles, you can swap any two cards within a cycle you've already examined.
Applying this to the last example above, we'd start decomposing as (1 7 3) (2 12 9 5 6 8 11 ...) and switch the JS and 2C. As a result, we'd change the given arrangement to one whose cycle decomposition is (1 7 3) (2 12 9 5 6 8) (4) (10 11), effectively breaking up an 8-cycle into a 6-cycle and a transposition.
"Inexact Iffy Verso" is an anagram of "X-Ray Vision Effect," and "Secondly, It's As Easy As ABC" is an anagram of "It's As Easy As No Bad Cycles."
Colm will do mathemagic with card demonstrations at book signings for his new Mathematical Card Magic: Fifty-Two New Effects at the CRC Press booth at 3pm on both Thursday 16th and Friday 17th January, at the 2014 Joint Mathematics Meetings in Baltimore. Readers attending this meeting may also wish to drop by the Martin Gardner Centennial booth (number 629, right across from the MAA pavilion).
For the ABC version, how hard is it to mentally check for a too long cycle? Here, a cycle of length 7 or more is too long, and one of length 6 or less is ok. If we can verify that 6 or more elements are in ok cycles, that tells us there can be no too long cycle. So, in the method described above, say you first find a 4 cycle, and then a 3 cycle. Then there are only 5 elements remaining and there cannot be a too long cycle. Or, if you find a 3 cycle and a 2 cycle, the next cycle must either be too long (and can be broken as explained) or not, in which case no cycle is too long. The worst case scenario is finding cycles covering just 5 elements, and then hitting a 7 cycle. That would require you to follow the complete cycle structure of the permutation. But most of the time you will either have a few short cycles (2,3, or 4) that are quick to follow, or hit a long cycle on the first or second go. I expect that with a little practice, one could survey the array of cards for a too long cycle and correct it with a transposition quite quickly.
ReplyDelete