Go up to Who Took The Last Coin?

Go forward to Discovering the Mathematics, Continued

Switch to text-only version (no graphics)

Go to University of Toronto Mathematics Network Home Page

The answer depends on how many of each type of coin there are. For
example, if you face a "(3,5,6) situation" (meaning 3 coins of one
kind, 5 of another kind, and 6 of a third kind), there's no way for
you to stop a clever opponent from eventually winning. So (3,5,6) is
a *losing situation*. (Try it
against the computer.
You can't beat it if you
start with (3,5,6).)

But if you face a (3,3,7) situation, there's a strategy you can
follow that guarantees you'll win. So (3,3,7) is a *winning
situation*. (Try this on the computer. Can you find the
way to beat the computer?)

**The Key Question.** Can you find some mathematical
pattern or condition that distinguishes the winning situations (like
(3,3,7)) from the losing ones (like (3,5,6))?

Play around with it for a while. Try to figure out which situations are winning ones and which are losing ones, and see if you can find any patterns. Play against the computer. When you've done as much as you can on your own, read on for some questions that'll help you discover the answer.

Wasn't that easy? The steps get harder as we go along, though.

**Step 2: What if there are two types of coins?** See if you can
answer the following questions:

- Is (1,1) a winning situation or a losing situation? (In other words, it's your turn, and there are two coins, of different denominations, on the table. Can you win?)
- What about (1,2), (1,3), (1,4), and so on? Are they
winning situations or losing situations? (
*Hint:*If you face a (1,*n*) situation with*n*>1, you can take away*n*-1 coins of the second type. Now your opponent faces a (1,1) situation). - Is (2,2) a winning situation or a losing situation?
(
*Hint:*Your only possible moves are to take one coin, leaving your opponent with a (1,2) situation, or to take two of the same denomination, leaving your opponent with a (0,2) situation). - What about (2,3), (2,4), (2,5), and so on?
(
*Hint:*Show that you can make a move which leaves your opponent with (2,2)). - Continue in this way. Try to formulate a conjecture
of the form
*the situation (*and see if you can prove it.*a*,*b*) is a losing one if and only if . . . - (a question to see if you really understand what's going on)
Why, in question 3, did you have to consider
*all*possible moves you could make, when in question 4, it was enough to consider only one move that you could make?

By now you should be convinced that your conjecture in question
5 is true. But how do you know for sure? How would you
*prove* it mathematically?

The key is this. Think about the condition you put in for the ". . . " in question 5. Are the following statements true?

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

**Step 3: What if there are three types of coins?** This
is harder. First, let's get a stock of examples of winning and losing
situations. Here's how to do this:

- Start with triplets of small numbers, like (1,1,1) (then work your way up to larger numbers).
- Ask yourself, "Is there a move I can make from this situation,
to turn it into a situation I already know is a losing one?" If the
answer is
*yes*, that means this situation is a*winning one*(because you can make a move that leaves your opponent with a losing situation). If the answer is*no*, go on to the next step. - Ask yourself, "Is it true that, no matter what move I make from
this situation, it will always be turned into a situation that I
already know is a winning one?" If the answer is
*yes*, that means this situation is a*losing one*(because no matter what move you make, your opponent will be left with a winning situation). - Sometimes you may not be able to answer yes to either
question. For instance, if you're thinking about the situation
(3,5,6) (rather than starting with small triplets as I suggested
above!), you won't be able to find a move that turns it into a known
losing situation, but you also can't say for sure that all moves turn
it into known winning situations. One possible move, for example,
would take away one coin from the group that has 5, leaving you with
(3,4,6), and you don't know yet whether (3,4,6) is a losing or
winning situation.
All this means is that you'll need to work on (3,4,6) and figure it out before you'll be able to figure out (3,5,6).

- If you start with triples of small numbers, figure them out, then move on to triples of larger numbers, you should eventually build up a large list of examples of situations you know to be winning ones and situations you know to be losing ones.

Here are some examples to get you started:

- Triples of the form (
*a*,*a*,*b*) with*b*>0 are always winning ones (because you can turn them into (*a*,*a*,0) which is a losing situation, as you should have figured out in step 2 when thinking about just two types of coins). - (1,2,3) is a losing situation, because the only situations it could turn into after your move are winning ones: (0,2,3), (1,0,3), or (1,2,0) (winning because of step 2), or (1,1,3), (1,2,1), or (1,2,2) (winning because they're each cases of the previous example).

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