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

Question

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?

user2661923 · Accepted Answer

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.

Christian Blatter · Answer

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

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

2 Answers

Add your own answers!

Ask a Question