You and a friend play a game in which there are an odd number of rocks. You can take 1, 2 or 3 rocks on your turn (alternating turns with your opponent); when all rocks have been taken, the person who has taken an odd number of rocks is the winner.

If you are the first to go, what strategy should you use in order to have the best chance of winning?

You must take an amount such that one of the following holds:

1. All you have taken so far, including the latest move, is odd and you leave 1 mod 8 for your opponent.

2. All you have taken so far, including the latest move, is odd and you leave 0 mod 8 for your opponent.

3. All you have taken so far, including the latest move, is even and you leave 4 mod 8 for your opponent.

4. All you have taken so far, including the latest move, is even and you leave 5 mod 8 for your opponent.

Why?

The first two are the ultimate win when leaving an actual 1 or 0 (nonmodular) for your opponent while having taken an odd number yourself.  Items 3 & 4 force your opponent to give you a winning option (again, at the end, with non-modular arithmetic).

For the higher values (so that mod 8 makes a difference):

In situation 1, you have taken an odd number and there's an odd number left for your opponent, so your opponent must have taken an odd number.  Now, left with 1 mod 8, he must take 1, changing his parity to even and leaving 0 mod 8; 2, keeping his parity at odd and leaving 7 mod 8; or 3, changing parity to even and leaving 6 mod 8. None of these is on the list of 4 winning moves.

In situation 2,  you have taken an odd number and there's an even number left for your opponent, so your opponent must have taken an even number.  Now, left with 0 mod 8, he must take 1, changing his parity to odd and leaving 7 mod 8; 2, keeping his parity at even and leaving 6 mod 8; or 3, changing parity to odd and leaving 5 mod 8. None of these is on the list of 4 winning moves.

In situation 3,  you have taken an even number and there's an even number left for your opponent, so your opponent must have taken an odd number.  Now, left with 4 mod 8, he must take 1, changing his parity to even and leaving 3 mod 8; 2, keeping his parity at odd and leaving 2 mod 8; or 3, changing parity to even and leaving 1 mod 8. None of these is on the list of 4 winning moves.

In situation 4,  you have taken an even number and there's an odd number left for your opponent, so your opponent must have taken an even number.  Now, left with 5 mod 8, he must take 1, changing his parity to odd and leaving 4 mod 8; 2, keeping his parity at even and leaving 3 mod 8; or 3, changing parity to odd and leaving 2 mod 8. None of these is on the list of 4 winning moves.

Any of the parities and mod values the opponent is forced to leave (that is, any set as viewed by your opponent, that's not on the list) allows you to return to one of the four winning types of move.

 

 

Posted by Charlie on 2004-04-20 15:10:56