Go backward to Discovering the Mathematics Behind the Game

Go up to Who Took The Last Coin?

Go forward to The Answer

Switch to text-only version (no graphics)

Go to University of Toronto Mathematics Network Home Page

Based upon this experience, we should expect that there's also some special mathematical condition that sets apart the losing three-coin situations. How can we find it?

Take each of your examples. Write the numbers in *binary
notation* (base 2). Write the three numbers underneath one
another. Now count the number of 1s in each column.

For example, with (3,5,6) (a losing situation), the numbers are 11, 101, and 110 in binary. Writing them underneath each other gives

11 |

101 |

110 |

1 |

100 |

101 |

Do this for all your examples. Can you find some special
characteristic when you calculate the number of 1's in each column
of a losing situation, that doesn't happen when you do it for a
winning situation? (*Hint:* When you calculate the number of
1's in a column, think about whether it's even or odd).

Once you've identified this special characteristic, see if you can
*prove* that this is what characterizes losing situations (and
that it's not just a fluke for the particular examples you've looked
at). Try to prove the following three things:

- If a situation has this characteristic, and its your turn, you cannot win in this turn.
- If a situation has this characteristic, then no matter what move you make, the situation will no longer have the characteristic after you move.
- If the situation doesn't have this characteristic, then you can make a move in such a way that the situation does have this characteristic after you move.

From these, you should be able to prove that your characteristic is exactly what determines whether or not a situation is a losing one. If one of these statements isn't true for your characteristic, go back and look for a different characteristic.

As a check on your work: you know that if one of the numbers is zero,
you're in the two-type-of-coin situation. This is a losing situation
if and only if the number of coins are equal (step 2). So, ask
yourself: suppose I have a triple of the form (*a*,*b*,0). In this case,
is the characteristic I've identified equivalent to the condition
*a*=*b*?

**Step 4: What if there are four or more types of coins?** You're
probably thinking that going from step 2 to step 3 was so hard, that
moving up to step 4 will be impossible. But no! If you think about
your characteristic from step 3, you should realize that, if you
phrase it properly, it can apply no matter how many different types of
coins you have. The proof you constructed in step 3 should work
regardless of the number of coins.

Congratulations! You have now come up with a mathematical way to look at a set of coins on a table, and tell, before the game even begins, which player will win (assuming both players play as well as is possible).

Along the way there was a lot of mathematical reasoning involved: looking at examples, seeing patterns, suspecting something to be true based on your observations, then finding out that it really is true by finding a proof of it. These are all essential ingredients to doing the kind of mathematics that you get to once you've covered the basic calculations and manipulations that you're spending most of your time on right now.

You might also like to think about what happens if you change the rule
so that the person who takes the last coin *loses*. It's a little
bit more complicated. But most of the time, the winning situations with
this rule are the same as the winning situations with the original rule.
The only difference in strategy comes when you get down to just a few
coins left.

**Note:** If you're really stuck finding the characteristic that
identifies the losing situations, you can
follow this link to
see the answer. But the task of convincing yourself that it's
true is still up to you!

This page last updated: May 26, 1998

Original Web Site Creator / Mathematical Content Developer: Philip Spencer

Current Network Coordinator and Contact Person: Joel Chan - mathnet@math.toronto.edu