davidbau.com

Heidi's got you beat.

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.

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?

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.

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 ...

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

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?

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.