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!"