# Nim Game remove $1,3$ or $4$ matches

Mathematics Asked on February 24, 2021

I was reading about variations of the nim game where 2 players remove matches from a pile of matchsticks.
In this variation players can remove $$1,3$$ or $$4$$ matches.
I can see that the player wins if the number of matches in the pile is:

{1, 3, 4, 5, 6, 8, 10, 11, 12, 13, 15, 17 ....}


and the player loses if the number of matches in the pile is:

{0, 2, 7, 9, 14, 16 ...}


It is not clear to me what is the pattern that indicates if the number of matches is a win.
I thought 4*2 = 8 (win) but also 4*2 + 1 = 9 (lose) so some multiple of the number of matches to remove is not a winning state.
What is the pattern here?

For the set $${1,2,3,4,5,6,7}$$ the losers are $${2,7}.$$

Inductively assume that for $${1,2,3, cdots, (7n-2), (7n-1), 7n}$$ the losers are precisely those numbers that are congruent to either 2 or 7, mod 7.

Consider the numbers $${(7n+1), (7n+2), cdots, (7n + 7)}.$$

(7n+1) can take 1, leaving (7n), so (7n+1) is a winner.

(7n+2) must leave (7n+1), (7n-1), (7n-2), which are all inductively assumed to be winners. Therefore, (7n+2) is a loser.

By very similar reasoning, (7n+3) through (7n+6) are winners and (7n+7) is a loser.

Correct answer by user2661923 on February 24, 2021

Let $$b_k=1$$ when $$k$$ is a winning number and $$b_k=0$$ otherwise. Doing the analysis the OP did somewhat further one quickly conjectures that $$(b_k)_{kgeq0}=(0,1,0,1,1,1,1,ldots) ,$$ where the $$ldots$$ suppress a periodic pattern with period $$7$$. That this pattern is true for $$0leq kleq 6$$ we know from looking at the computed table.

It remains to set up an induction proof: For each of the seven remainders mod $$7$$ we go back the necessary steps and verify that everything suits. The inductive hypothesis is: The pattern is true for all $$k≤7j−1$$. The induction is with respect to $$j$$, and the base case is $$j=1$$.

Answered by Christian Blatter on February 24, 2021