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
Discovering the Mathematics Behind the Game
If you play as well as you possibly can, and so
does your opponent, who will win? The one who starts, or the one who
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.
Step 1: What if there's only one type of coin? Then you can
just take all the coins. You've won, because you took the last
coin. So any situation with only one type of coin is a winning
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
- Continue in this way. Try to formulate a conjecture
of the form the situation (a,b) is a losing one if and only if
. . . and see if you can prove it.
- (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?
Can you see how to turn these statements into a proof that if the
condition holds, it's a losing situation, and if the condition doesn't
hold, it's a winning situation?
- If the condition holds, and its your turn, you cannot win in
- 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
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:
Now it's up to you to figure out more examples. Once you have a lot,
see if you can find some mathematical characteristic that
distinguishes the losing situations from the winning
ones. (Hint: think about writing the numbers in base 2). If you
can figure it out on your own, consider yourself an exceptionally
gifted mathematician! If not, move to the next section after you've thought about
it for a while.
- 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
This page last updated: May 26, 1998
Original Web Site Creator / Mathematical Content Developer:
Current Network Coordinator and Contact Person:
Joel Chan - email@example.com