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

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

2 Answers 2


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.


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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