Discovering the Mathematics Behind the Game

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.

Discovering 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:

1. 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?)

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

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

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

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

6. (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?

1. If the condition holds, and its your turn, you cannot win in this turn.
2. If the condition holds, then no matter what move you make, the condition will no longer hold after you make it.
3. 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:

1. Start with triplets of small numbers, like (1,1,1) (then work your way up to larger numbers).

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

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

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

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