How many toothpicks are needed to win.

[westgrant88]

Consider the following two-player game. Player One places between 50 and 60 toothpicks on the table. Player Two picks up at least one and no more than nine of the toothpicks. Player One then picks up at least one and no more than nine of the remaining toothpicks. Play alternates in this way until there are no more toothpicks remaining on the table. The person who picks up the last toothpick from the table loses. If you are Player One, how many toothpicks should you place on the table to guarantee a win for yourself?

 

[BobG]

Spoiler

If you mean 50 to 60, inclusive, then either 50 or 60 will work. If you mean between 50 and 60 (in other words you can place 51 to 59 toothpicks, then Player 1 is guaranteed to lose if Player 2 knows how the game is played. You always want the opponent to wind up with a multiple of 10 when it's their turn to remove toothpicks.

 

[nashsur]

I'm sorry BobG got it backwards. You always want for you to have ten or more tooth picks on the table. Player 1 can put down any number over 55 to assure a win. Example: each player picks up 9 three times. It is players ones turn. There are only six left. He picks up five. Almost any combination that leaves player one with the NEXT TO LAST move and there is more than one tooth pick on the table has him winning.

 

[D H]

Short and sweet version:

Spoiler

51. Anything else is a guaranteed win for player #2.

Detailed version:

Spoiler

If player one puts down just one toothpick it is a win for player one because player two must pick up at least one toothpick. If player one puts down N=2 to N=10 toothpicks, player two can pick N-1 toothpicks, leaving a situation in which player one must pick the last toothpick. Putting down 11 toothpicks once again guarantees a win for player one. Player two must pick up 1≤n≤9 toothpicks. Player one picks up 10-n toothpicks, forcing player two to pick the last. N=12 to N=20 is again a losing setup for player one; player two takes just enough to reduce the heap to 11 toothpicks.

By recursion, player one putting down n*10+1 guarantees a winner for player one. Anything other than n*10+1 guarantees a win for player two.

 

[D H]

I'm sorry BobG got it backwards.

Correct. He didn't read the instructions. This is a misère game, not a normal game.

Player 1 can put down any number over 55 to assure a win.

Nope. You're player 1, I'm player 2. Suppose you put down 55 toothpicks. I'll take 4, leaving a pile of 51 for you to draw from. No matter how many you take, I can always take 10 less that, leaving a pile of 41 for you to draw from. You'll pick again and I'll reduce the pile to 31. After the next round I'll reduce it to 21, then to 11 on the round after that, and finally to 1 on the round after that. You have but no choice to take that last toothpick, so you lose.

 

[BobG]

I'm sorry BobG got it backwards.

Correct. He didn't read the instructions. This is a misère game, not a normal game.

So true. I was thinking whoever picked up the last toothpick won.

 

[nashsur]

I too made a mistake. I thought player 1 also picked up toothpicks first. After rereading the instructions, I now say that player one must put 51 or n*10+1 in order to win. I stand corrected.