Foregone Outset

This year's Mathematics Awareness Month theme—Mathematics, Magic and Mystery—is inspired by the extensive written legacy of Martin Gardner, the best friend mathematics ever had, who passed away four years ago at the age of 95.5. Martin was a great believer in the power of curiosity and play in the learning and advancement of mathematics.
                  
Among the 30 separate Mathematics Awareness Month webpages of topics and activities on offer for students, teachers, and curious people of all ages—not just in April 2014, but at any time after that—are several that involve cards. These include Bob Hummer parity-based amusements, the ternary arithmetic of the 27 Card Trick, our own additional certainty effect, and the wonderful mathematics of perfect shuffling (and unshuffling).

Coins of the Realm

In due course below, we offer a further card diversion inspired by a Martin Gardner puzzle. In a way, it's a companion piece to our last Card Colm musings on the "Postage Stamp Issue." It's related to a well-known coin problem. Let's start by reviewing "Coins of the Realm"–a problem Martin posed in an old Scientific American column, from June 1964. It's included in Chapter 12 of his Sixth Book of Mathematical Games from Scientific American (W. H. Freeman, 1971), and in the following form in Chapter 1 of his The Colossal Book of Short Puzzles and Problems (Norton, 2006, edited by Dana Richards).

In this country at least eight coins are required to make the sum of 99 cents: a half-dollar, a quarter, two dimes and four pennies. Imagine you are the leader of a small country and you have the task of setting up a system of coinage based on the cent as the smallest unit. Your objective is to issue the smallest number of different coins that will enable any value from 1 to 100 cents (inclusive) to be made with no more than two coins. 

For example, the objective is easily met with 18 coins of the following values: 1, 2, 3, 4, ... 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90. Can you do better? Every value must be obtainable either by one coin or as a sum of two coins. The two coins need not, of course, have different values.

Martin gives two 16-coin solutions, as follows.

1, 3, 4, 9, 11, 16, 20, 25, 30, 34, 39, 41, 46, 47, 49, 50

is listed as being given in Roland Sprague's Recreation in Mathematics, and is good for precisely the range 1—100.

1, 3, 4, 5, 8, 14, 20, 26, 32, 38, 44, 47, 48, 49, 51, 52

is listed as having been provided by Peter Wegner, and is good for the larger range 1—104.

Annealing Twofer Whimsy

It's time to re-engage willing participant Willa from the last Card Colm. Take out a deck of cards and shuffle them a little. Deal out sixteen cards in a face-down row, and produce and a piece of paper on which is written a vertical list of the counting numbers from 1 to 20, along with a pen.

Say, "Willa, we're going to play a game. First we'll take turns picking cards from this row until each of us has eight, then we'll try to 'make change' for any amount on this list, using one or two cards from our personal selections. We'll keep track on this piece of paper."

For instance, to make change for 1, each of you needs an Ace, and for 2 either two Aces or a 2. On the paper write Ace next to the 1, and either Ace + Ace or 2 beside the 2. Suits play no role here. You manage to make change for all amounts up to 14, but poor Willa gets stuck long before that. Say something consoling, such as, "I hope you don't think that was a foregone conclusion from the outset."

Say, "Bad luck. Let's try with this other deck. We've exhausted the supply of Aces in that one." Proceed as before, this time letting Willa go first. The results are even better for you, however, as you make it to 15 on the list.

There are three key points here which we haven't mentioned: the cards used are far from random, the shuffling doesn't disturb the top third of the deck, and the "taking turns" picking cards is also rigged in your favor.


As to the cards, the first time around the sixteen cards consist of two Aces, a 3, a 4, two 5s, an 8, and a King, in any order, in the odd-numbered positions considered from left to right. Note that 1, 3, 4, 5, and 8 form the start of the Wegner list above. These cards, shown above, allow for any total from 1 to 14, using one or two at a time.

The cards in the even-numbered positions, shown below, are an Ace, a 2, a 3, and a 5, along with four royal cards. This does not allow for a total of 9 or 10.



Thanks to the "Martin Gardner's Coins to Cards Effect" principle in "Better Poker Hands Guaranteed," you can force Willa to take the cards in the even-numbered positions, leaving the other, winning ones, for you. Here's how: Cards are always picked from one of the two ends of the ever-shrinking row, and you start by picking the card in the first position. Thus Willa's first selection is one of the cards in positions two or sixteen. Next, after pausing as if deliberating carefully, you take the card beside the one she selected, hence one of the cards in positions three or fifteen. Continuing in this way, always taking cards in odd positions, you'll force her to select cards in the even positions, and all will work according to plan. You'll get two Aces (you need two to be able to make change for 2), a 3, a 4, two 5s (both are needed to make change for 10), an 8 and a King; she'll get the others.

The second time around, use the next sixteen cards in the deck, which consist of two Aces, two 3, two 4s, a 9, and a Jack, in any order, in the odd-numbered positions. Note that 1, 3, 4, 9, and 11 form the start of the Sprague list above. These cards, it can be checked, allow for any total from 1 to 15, again using one or two cards. The other eight cards, in the even-numbered positions, are an Ace, two 2s, a 5, along with four cards of value 9 or above. This does not allow for a total of 8. How cruel life can be.

Some entries at The On-Line Encyclopedia of Integer Sequences may be of interest here, such as Sequence A001212.

Opponent Retaliations

There's another way to give the illusion of free choice to Willa while actually being able to guarantee that she'll get the eight cards you want her to. This time, stack the eight cards you want on top of the deck, with the eight she's doomed to get underneath those. Deal sixteen cards to the table, thus putting the cards you want at the bottom. Now, pick up that packet and do the sixteen-card version of what is explained in "Bill Simon's Sixty-Four Principle" for eight cards. The result is that you get the bottom eight cards as desired.

One advantage of this approach is that you can opt to focus on just your winning cards, by only stacking the ones you want on top at the beginning, maintaining them there throughout some fair-seeming shuffling. This means that Willa's cards will be entirely left to chance, and will be unlikely to contain sufficiently many small values for her to even get started on the list. That being the case, you can either start trying to make change at 3 or 4, not 1, or you could reverse the roles and let Willa win each time, by modifying who gets which pile.

---

"Foregone Outset" is an anagram of "Goes to Fourteen," and "Annealing Twofer Whimsy" is an anagram of "Winning Ways of the Realm." "Opponent Retaliations" is an anagram of "Presentational Option."