Develop a winning strategy for a game

Question

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.

Answer 1

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$.