Friday, February 28, 2014

Postage Stamp Issue

There's no denying that the theme and spirit of Mathematics Awareness Month 2014 is inspired by the landmark book Mathematics, Magic and Mystery (Dover, 1956) by legendary writer Martin Gardner, the best friend mathematics ever had.

title      title 

The beautiful MAM 2014 poster on the right here, a high resolution version of which can be downloaded, was designed by Bruce and Eve Torrence of Randolph-Macon College. It echos many of Martin Gardner's most beloved motifs: magic squares, knots, geometric vanishes, Möbius bands, illusions, and playing cards.

The Alumni Midterms

Did somebody mention cards? For us, Martin's extensive legacy has proved to be a rich source of ideas for amusements with cards, going back to 1999, and many of these have surfaced in Card Colms. It seems appropriate, in his centennial year, to focus on new card activities derived from things Martin wrote about. What follows may serve as a way to generate interest in a classic combinatorial problem.

Find a willing participant; let's call her Willa. A red-backed deck and a blue-backed deck are produced, and you quickly run through the cards in each deck face up, tossing aside all Jacks, Queens, and Kings. "We won't need those," you say, before giving Willa free choice of the two slimmed-down decks. Assume she takes the red deck and you take the blue one.

Say, "Willa, let's play a game. We'll first do it with your deck, then we'll try it with mine. First you need to shuffle the cards. Please split the red deck roughly in the middle, and riffle the two resulting halves together." While Willa is shuffling, produce a pen, and a piece of paper on which is written a vertical list of the counting numbers from 1 to 30.

Continue, "Please lift off the top half of those shuffled cards, as best you can estimate, it doesn't have to be precise. I get the other half." Set aside your half for later. "Now, please take about half of your cards, that should be ten cards, roughly. Your goal it to see how high you can get on this list, using at most three of these random card values added up, I'll keep track for you. Please look at your card faces, do you have an Ace? Great!" She does, and you write write A next to the the 1 on the list. Next to the 2 write either 2 or A + A, depending on whether she has a 2 or two Aces. Keep going as long as is possible, beside each number writing the values of cards she has which equal or add up to that number.

The first time three card values are used, pause, and say, "Sorry, I forgot to mention that to make it more interesting, whenever you have three card values making up a particular number, you must use one of those cards again for the next number. Got it?" Since, you only just sprung this surprise on Willa, offer her the chance to redo that first three-value sum if she wants to.

The result of Willa's efforts might be all numbers from 1 to 16 (or some other number) achieved, before she failed to get 17 subject to the "continuity" condition when using three cards. Have Willa do it all over, with the other roughly ten cards of her half deck, and another copy of the list. The results should be along the same lines.

Yet, when you do the same with your cards, in two approximately 10-card palettes just like Willa, with her keeping track this time, on new copies of the list, you should do much better, getting to 25 or maybe even higher.

The deck is rigged of course. Suits are irrelevant. You want to end up with three 4s and 5s in in your initial twenty cards, with Willa only getting one each of those values in hers. Furthermore, you arrange it to that each of you starts with an Ace and a 2 in each of your 10-card card palettes, otherwise it's hard to get started! It turns out that having several 4s and 5s helps you to beat her.

Here's a suggested set-up, consisting of four 10-card packets.

Packet A is these cards in this order, from the top down: any Ace, 2, 5, 7, 8, 4, 2, Ace, 7, 8.

Willa will end up with most of these, and the first and internal Ace and 2 for sure. You're letting her have one 4 and one 5 to deflect suspicion, otherwise, she may notice upon repetition that she never had a 4 or a 5. It turns out that if you had all four of each (and even more Aces) you'd be sure of getting to at least 15.

Packet B is these cards in some jumbled order: all of the 3s and 6s, and two of the 7s.

You will end up with most of these.

Packet C is these cards in some jumbled order: all of the 9s and 10s, and two of the 8s.

Willa will end up with most of these.

Packet D is these cards in this order, from the top down: any 4, 5, Ace, 2, 5, 5, 4, 4, 2, Ace.

Most importantly, you will end up with most of these, and the internal and last Ace and 2 for sure.

Stack A on top of B, on top of C stacked on top of D. Randomly insert the Jacks, Queens and Kings; they're only to add to the illusion of fairness, as they are pulled out again at the start of the effect. When Willa splits the resulting 40-card deck, she more or less riffle shuffles A and B into C and D.

Furthermore, when she takes the top half of that for herself, she should get most of A and C, in such a way that the final split into two roughly 10-card packets gives her an Ace and 2 in each. Similar conclusions apply to the cards you end up with, which are more or less B and D.

The restriction about having to reuse one of three cards used for a previous sum is designed to make it harder for Willa to win.

It can be repeated with the other deck, which we suggest arranging in an order which exactly mirrors the type of set-up just proposed, i.e., runs in the opposite order. That way, you can take a gamble on saying, "Let's try that again. Maybe you'll have more luck if you take the bottom half of the deck this time." You may want to vary the card set-up a little so Willa doesn't realize that she's been duped a second time.

We now explain the mathematics underlying this game.

Aha! Little Poet

title      title

This month's Card Colm was inspired by Martin's science fiction puzzle tale "The Postage Stamps of Philo Tate" on page 15 of Mathematical Puzzle Tales (MAA, 2000), which is a reissue of Science-Fiction Puzzle Tales (Potter, 1981). That tale concerns the classic postage stamp problem (see Wikipedia and MathWorld).

Postage stamps in D different demoninations (or values) are available. What amounts of postage can be made up using at most S stamps, where stamps of any denomination (or value) may be repeated?

For instance, if D = 2, the values being 1 and 2, and S = 2, clearly we can make up 1, 2 (in two ways, as 2 or 1 + 1), 3 = 1 + 2 and 4 = 2 + 2, and no other amounts are possible. On the other hand, if D = 2 and the values are 1 and 3, and S = 2 again, then we can make up 1, 2 = 1 + 1, 3, 4 = 1 + 3, and 6 = 3 + 3, and no more amounts are possible. Note that 5 is not possible.

The goal is to be able to make as a large an unbroken range 1 to R as possible using the available stamps, subject to a restriction on how many stamps can be used. In both examples above—where we can use up to two stamps of two values—it's 1 to 4. However, if D = 2, the values being 1 and 5, and S = 2, then 3 is not possible, so R = 2 this time. Obviously, we must always include 1 in the values allowed to even get started.

If D = 3, the values being 1, 2 and 5, and S = 2, then it can be checked that 1 to 7 are possible, as is 10, but not 8 or 9. Here R = 7.

If D = 3 again, with values 1, 2 and 5, but S = 3, then it can be checked that 1 to 12 are possible, but not 13 or 14, though 15 is. Here R = 12.

The following table lists some of the optimal results when S = 3, i.e., when we use up to 3 stamps of various values, for various numbers D of denominations or values. Additional information can be found in Sequence A001213 in The On-Line Encyclopedia of Integer Sequences. One entry in the table is intentionaly left blank; filling it in correctly leads to a pleasant surprise or two.

Using up to 3 stamps
D = # of values values range 1 to R
2 1, 3 1 to 7
3 1, 4, 5 1 to 15
41, 4, 7, 81 to 24
51, 4, 6, 14, 151 to 36
6?1 to 52

If we consider specific small values of D, for any S, then the maximal R are given by the following entries at The On-Line Encyclopedia of Integer Sequences,

D = 2 values, S = n stamps: Sequence A014616

D = 3 values, S = n stamps: Sequence A001208

D = 4 values, S = n stamps: Sequence A001209

D = 5 values, S = n stamps: Sequence A001210

D = 6 values, S = n stamps: Sequence A001211

Likewise, if we consider specific small values of S, for any D, then the maximal R are given by these entries at The On-Line Encyclopedia of Integer Sequences

D = n values, S = 2 stamps: Sequence A001212

D = n values, S = 3 stamps: Sequence A001213

D = n values, S = 4 stamps: Sequence A001214

D = n values, S = 5 stamps: Sequence A001215

D = n values, S = 6 stamps: Sequence A001216

Information about arbitrary values of D and S is coded in this sequence: 

D = k values, S = n stamps: Sequence A084193

Readers still in search of a little thrill may enjoy recent reflections on some old magic and the recycling of the principle from the first Card Colm over at the Huffington Post's "Magical History Tour." 

"The Alumni Midterms" is an anagram of "Three Summand Limit" (so is "The Untrimmed Mails"), and "Aha! Little Poet" is an anagram of "Philo Tate Tale!" 

Tuesday, December 31, 2013

X-Ray Vision

We embark on the centennial year of Martin Gardner, the best friend mathematics ever had, with a seemingly-impossible, X-ray vision effect we feel he would have enjoyed. Gardner's extensive legacy inspired the theme of Mathematics Awareness Month 2014. The MAM2014 poster will be unveiled at 11:30am on Thursday 16th January 2014, at 11:30 a.m. at the MAA Pavilion in the exhibit hall at the Joint Math Meetings in Baltimore.

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:

It turns out that there is a way to guarantee that all four
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":

04    03    02    01
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:

All four succeeded in finding their cards within seven tries,
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:

The probability of any number of people all finding pre-assigned cards
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).