## June 02, 2007

### 99 Cent Game

Heidi and David are in Hawaii on vacation and buy a cone of Dole Whip, which comes to \$2.01 after tax. The cashier gives Heidi three quarters, a dime, two nickels, and four pennies.

"I hate getting 99 cents of change," says Heidi.

"Ah hah, but then you can play the 99 cent game," replies David.

David explains the rules:

Heidi will arrange her ten coins in a single line, in any order she likes.

Then, starting with David, each of them will take turns taking a coin from one of the two ends of the line, until each has five coins.

In the end, whoever has more money wins.

This simple game is actually pretty fun. You can play it with any handful of coins, and it is not obvious what the best strategy is. But there is a simple winning strategy.

If Heidi gets to place the coins and David goes first, which player has a winning strategy, Heidi or David?

Posted by David at June 2, 2007 06:32 PM

Heidi's got you beat.

Posted by: Peter H at June 4, 2007 08:13 PM

Well, I agree that Heidi has to win, b/c David wouldn't post a puzzle where he makes Heidi a guaranteed loser. Would he?

I assume that you can simplify the game to have 7 pennies and 3 quarters, since winning two quarters is the only thing required to win either game. Where should Heidi place the quarters? I can't figure out a sequence to guarantee a win for her. For every sequence I come up with (well, all 5 that i tried), there's a way for David to get two quarters.

Posted by: Kevin B at June 5, 2007 02:09 AM

Nope, I'm a meanie.

David has a guaranteed win, regardless of how Heidi places the coins. In fact, David can win with any set of coins of any denomination as long as the number of coins is even (so they both get the same number of coins), and as long as the total amount of money is odd (to prevent ties).

How?

Posted by: David at June 6, 2007 05:35 AM

We played this with our grandson (who was delighted with it!)

He beat me every time and explained his strategy this way: "I'll let you go first Grandma because I want to arrange the coins." (Okay letting ME go first? That's a change!) Then he explains that he groups the weakest coins (his words) together and then alternates the "strong" coins between the weak ones. Finally he places one of the "weakest" coins at each end and then invites me to go first with a big grin!

I was fascinated by his use of the word "weak" for a penny and "strong" for a quarter.

Posted by: Mary at June 8, 2007 10:27 AM

I forgot to mention that our grandson is 7.

I keep reading this blog for posts like these ... I'm dying to teach him Phython and just waiting for the right time to draw him in ...

Posted by: Mary at June 8, 2007 10:29 AM

David easily wins if he goes first.

Part 1.

The key is the 3 quarters. Two quarters make 50 cents, which is more than the sum of all the other coins combined. Since there are 3 quarters in the game, somebody HAS TO end up with at least 2 of them; that person wins. (in fact, we could now forget about any specific denominations and substitute binary "1"'s for quarters, and "0"'s for non-quarters, and play to get 2 "1"'s).

Part 2.

Let's assume the coin positions are numbered 0 to 9, and that David and Heidi take consecutive coins from the left, David starting.

0123456789
DHDHDHDHDH

After David's move Heidi can pick either 1 or 9, both odd-numbered positions. Whichever, she picks David can continue to pick even-numbered coins, forcing Heidi to stay w/ odd-numbered ones. Once he chooses even or odd positions, he can defend this invariant! Now, w/ 3 quarters in the game, two have to be either odd or even. David therefore picks even or odd positions respectively, starts with 0 for even, or 9 for odd, and just shadows Heidi's picks to continue having access to even or odd numbered coins.

This is an interesting case of a "defensible invariant."

Posted by: Jacek Ambroziak at June 14, 2007 01:11 PM

Excellent!

The strategy works for any combination of coins, as long as there are an even number of coins with an odd sum.

If there are an odd number of coins, it is easy to arrange a loss for the first picker, even though he gets the extra coin. I find it amusing that parity plays such a role in a game that is played only on the ends.

Do you know any other cute games that can be played with a pocket full of change?

Posted by: David at June 18, 2007 12:33 PM

It is one of these puzzles that can take a while to solve (it took me a few whiles :-) ) but that, once solved, seem complete nobrainers. Here's another way to describe the solution.

Imagine any even number of coins of arbitrary denominations arranged in a sequence. Now imagine that the coins lie on alternating black and white fields. Assume that the first field is white, and therefore the last one must be black. It is easily seen that once David "picks a color" by taking either the 1st or the last coin, he can continue picking same-colored coins till the end (leaving all the opposite colored fields for Heidi). If he prefers "white coins" to black ones, 'cause they sum up to a higher value, he can have them!

A similar "coloring method" works for another puzzle, the "mutilated chessboard" problem, where 2 diagonally opposite tiles are removed, and the question is whether the 64-2=62 tile chessboard can be covered by 2-tile domino pieces.

Posted by: Jacek Ambroziak at June 18, 2007 02:51 PM