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

  • What does it mean to "pick a or b match stick"? – joriki Aug 8 '12 at 16:11
  • Suppose there are 10 matchstick at table, – Arpit Bajpai Aug 8 '12 at 16:12
  • You can pick either 1 or 2 in your turn – Arpit Bajpai Aug 8 '12 at 16:13
  • So $a$ and $b$ are arbitrary fixed integers, and each move consists in removing either $a$ or $b$ matchsticks from the table? – joriki Aug 8 '12 at 16:13
  • yes we need value of N in terms of a and b for winning startegy and then winning strategy – Arpit Bajpai Aug 8 '12 at 16:17
up vote 0 down vote accepted

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.

  • This is the subtraction game, a variant of Nim. – joriki Aug 9 '12 at 6:00
  • More specifically it is misère subtraction, since in this case the last player to move loses. – Théophile Aug 10 '12 at 18:06

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.