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

$\endgroup$
7
  • $\begingroup$ What does it mean to "pick a or b match stick"? $\endgroup$
    – joriki
    Commented Aug 8, 2012 at 16:11
  • $\begingroup$ Suppose there are 10 matchstick at table, $\endgroup$ Commented Aug 8, 2012 at 16:12
  • $\begingroup$ You can pick either 1 or 2 in your turn $\endgroup$ Commented 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
    Commented 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$ Commented Aug 8, 2012 at 16:17

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This is the subtraction game, a variant of Nim. $\endgroup$
    – joriki
    Commented 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
    Commented Aug 10, 2012 at 18:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .