(IMAGE) Go backward to Discovering the Mathematics Behind the Game
(IMAGE) Go up to Who Took The Last Coin?
(IMAGE) Go forward to The Answer
 (SWITCH TO TEXT-ONLY VERSION) Switch to text-only version (no graphics)
(IMAGE) Go to University of Toronto Mathematics Network Home Page

Discovering the Mathematics, Continued

In the case of two coins, most of the situations were winning ones. It was a special class of situations, namely those pairs (a,b) with a=b, that were losing ones.

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
and there are two 1's in each column. For a second example, the triple (1, 4, 5) (also a losing situation) would be written
and the number of 1's in the various columns are 2, 0, and 2 (two 1's in the leftmost column, none in the middle, and two in the rightmost column).

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:

  1. If a situation has this characteristic, and its your turn, you cannot win in this turn.
  2. If a situation has this characteristic, then no matter what move you make, the situation will no longer have the characteristic after you move.
  3. 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 -