5
$\begingroup$

There are $N$ matchsticks at the table. Two players play the game. Rules: (i) A player in his or her turn can pick $a$ or $b$ match sticks. (ii) The player who picks the last matchstick loses the game.

  1. What should be the conditions on $N$ so that a winning strategy can be derived for the first player?

  2. What should be the strategy of first player so that he or she always wins this game provided $N$ is such that a wiinning strategy can be derived?

I have solved this problem by hit and trial for small numbers one or two, but is there a general solution?
Edit : Suppose rules of the game are changed and now a player in his or her turn can pick any number of matchstick upto p < N , then how many sticks should first player pick to ensure a win

  • 0
    Last player has to pick remaining match stick2012-08-08

2 Answers 2

0

With the current edit, the game goes like this:

There are $N$ matchsticks on a table, two players (Left and Right) and a pre-ordained number $p$. Play alternates between Left and Right, with Left starting, and on a player's turn that player may remove up to $p$ matchsticks from the table. The person who takes the last matchstick loses.

So you ask how Left can guarantee a win. The answer is that he can't always guarantee a win. For example, suppose $p = 1$ and there are 3 matchsticks. He picks up 1, Right picks up 1, and left picks up the last one, losing.

But Left can always win unless $N = kp + (k + 1)$ for $k \geq 0$. Why is this?

If $N = 1$, Left loses. Ok. If $N = 2$, Left picks one up. If $N = 3$, Left picks 2 up. This works until $N = p + 1$, when Left picks up as many as he can take, $p$. At $p + 2$, no matter how many Left picks up, there are a number of sticks that allow Right to win (Right just has to use the strategy that Left would have used). But at $p + 3$ sticks, all that Left has to do is pick up $1$, landing Right in the losing position $p+2$. This works until $2p+2$, when Left can pick up exactly $p$. At $2p + 3$, Left loses as no matter what move Left does, Right can use the strategy we described above for Left.

For example, suppose $N = 14$ and $p = 5$. Then Left wants to move the game to a 'losing position' $kp + (k + 1)$. Here, that means moving to $2(5) + (2 + 1) = 13$, by picking exactly one up. No matter how many Right picks up, Left's next move will be to $1(5) + (1 + 1) = 7$ (i.e. after Left moves, there will only be $7$ sticks on the table). As this is $6$ away from $13$, Right can't move there. Left's next move will be to exactly $1$ stick on the table.

So $N = kp + (k+1)$ are the 'losing positions' of the game.

  • 0
    More specifically it is *misère* subtraction, since in this case the last player to move loses.2012-08-10
1

If the moves consist of taking either $a$ or $b$ sticks, with $a\lt b$ and, as clarified in a comment, $N\lt a$ is a loss, then the first player wins iff $((N-1)\bmod(a+b))\bmod(2a)\lt a$, and a winning strategy is to take $a$ sticks if $(N-1)\bmod(a+b)\gt b$, take $b$ sticks if $(N-1)\bmod(a+b)\lt a$, and take either otherwise.