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

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP