Math Olympiad problem (Oct 4)

sirio11 · #1 10-04-2007, 01:51 PM

Two players play a game starting with 153 counters. Taking turns, each player must remove between one and nine counters from the game. The person who removes the last counter wins. Does either the first player or second player have a guaranteed winning strategy, and if so, what is it?

Phil153 · #2 10-04-2007, 02:01 PM

<font color="white">The key is working backwards. The first person to leave 10 counters wins. Which means the first person to leave 20 counters win. Which means the first person to leave 30 counters wins. And so on. The first person to leave 10x counters wins, since that person can always game the situation to force the second person to always have 10x counters. So, the first person always wins, and his strategy is to go the nearest 10.</font>

Cueballmania · #3 10-04-2007, 04:48 PM

<font color="white"> Using the strategy stated above, player 1 will win using the strategy of first picking 3. Then continuing with the strategy of choosing x, where x=10-player2's number.</font>

jogsxyz · #4 10-04-2007, 05:13 PM

[ QUOTE ]
Two players play a game starting with 153 counters. Taking turns, each player must remove between one and nine counters from the game. The person who removes the last counter wins. Does either the first player or second player have a guaranteed winning strategy, and if so, what is it?

[/ QUOTE ]

Is this really the game? Shouldn't it be the person who forces the other player to remove the last counter is the winner?

TomCowley · #5 10-05-2007, 05:37 PM

The solution to both problems is as close to identical as they get. I also solved this game for 1-3 counters at a time. When I was 5. Seriously. Why is this on an Olympiad?

sirio11 · #6 10-05-2007, 08:07 PM

[ QUOTE ]
The solution to both problems is as close to identical as they get. I also solved this game for 1-3 counters at a time. When I was 5. Seriously. Why is this on an Olympiad?

[/ QUOTE ]

Tom, there are several levels on the Olympiad, from elementary school to high school students, obviously this was not in the IMO, but I just like to choose problems because of its beauty. I mean I could ask the forum to solve Golbach's conjecture, but what's the use.
Even in the IMO usually there is a pretty simple problem so contestants from several countries can solve at least one problem.

Phil153 · #7 10-05-2007, 08:40 PM

Please don't get discouraged - I really enjoy you posting these - but this one in particular was a little too easy. [img]/images/graemlins/smile.gif[/img]

sirio11 · #8 10-05-2007, 08:40 PM

Oh, and try now to solve the general problem, n counters and players remove between one and m

Same solution?

hitch1978 · #9 10-05-2007, 08:43 PM

Just leave a denomination of M+1, no?

Phil153 · #10 10-05-2007, 08:50 PM

I thought you meant "n counter and n players" at first. Without thinking about it, that might be an interesting problem from a game theory perspective if deals were allowed.

For n counters and 2 players, first player takes away n mod (m+1) counters, then (m+1-k) counters on each turn, where k is the number of counters your opponent removes on their turn.