3
$\begingroup$

Okay so I've been going crazy about this problem I was given. It is as follows:

Given a pile of N matches, 2 people take turns removing matches from the pile. When it is your turn you are allowed remove 1, 5 or 6 matches. If it is your turn and you are unable to make a move then the game is over and you have lost.

The idea is to develop a strategy where you can always win. Note that you can always decides who goes first.

Not sure if I'm even on the right track but currently I can guarantee that if it is my go and then I remove 1, 5 or 6 matches, leaving my opponent with 22 matches I will win. But unsure how to guarantee that this situation will arise.

Any help would be appreciated even if it's just a reassurance that it is possible because I've spent hours within the last 2 days and still can't come up with a winning strategy that works all the time.

$\endgroup$
1
$\begingroup$

The nature of a position in this game depends only on $n \bmod{11}$. If $n \equiv 0,2,4 \pmod{11}$ then $n$ is a losing position, otherwise it is a winning position. You can prove this by induction by showing that (1) every move from a losing position leads to a winning position, (2) at every winning position one can move to a losing position. This can be checked by exhaustive case analysis:

  • $0 \bmod{11}$: moves lead to $5,6,10 \bmod{11}$, all winning positions.
  • $1 \bmod{11}$: removing 1 match leads to $0 \bmod{11}$, a losing position.
  • $2 \bmod{11}$: moves lead to $1,7,8 \bmod{11}$, all winning positions.
  • $3 \bmod{11}$: removing 1 match leads to $2 \bmod{11}$, a losing position.
  • $4 \bmod{11}$: moves lead to $3,9,10 \bmod{11}$, all winning positions.
  • $5 \bmod{11}$: removing 1 match leads to $4 \bmod{11}$, a losing position.
  • $6 \bmod{11}$: removing 6 matches leads to $0 \bmod{11}$, a losing position.
  • $7 \bmod{11}$: removing 5 match leads to $2 \bmod{11}$, a losing position.
  • $8 \bmod{11}$: removing 6 match leads to $2 \bmod{11}$, a losing position.
  • $9 \bmod{11}$: removing 5 match leads to $4 \bmod{11}$, a losing position.
  • $10 \bmod{11}$: removing 6 match leads to $4 \bmod{11}$, a losing position.

For completeness, the $g$ values are $0,1,0,1,0,1,2,3,2,3,2$ (and then they repeat).

Your strategy is as follows: if $n$ is a winning position you start, otherwise you go second. Then you follow the strategy outlined above, which is guaranteed to win.

This strategy can be computed mechanically using the Sprague–Grundy function $g$.

$\endgroup$

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.