combinatorial game of sheets

37 Views Asked by At

We have an odd number of sheets organized in a pile. We have two players, and every player can remove $1,2,5$ or $6$ sheets, and keep them by their side. The winner is the player(s) that have even number of sheets at the end ($8,6,4,2$).

How can I find a strategy that always wins? (You can decide whether or not to start so you can win). If you can find any mathematical relations / strategies please help me.

The players know how many sheets there are, since the first number of sheets is odd they wouldn't both have even number of sheets at the end for example number $3$. If player one started and removed $2$ then player two have to remove $1$, the winner is player $1$ since he has even number at the end...

1

There are 1 best solutions below

2
On BEST ANSWER

Winning strategy:

Go first if n mod 4 == 3 (i.e. if there are 3, 7, 11, 15 etc. sheets), go second otherwise.

If you go first, take 2 (or 6) sheets.

On every other turn, if their previous move was odd (1 or 5) take either 1 or 5 sheets yourself. If the previous move was even (2 or 6), take either 2 or 6 sheets yourself. With one exception that if there's only one sheet left just take the one sheet regardless of how you got there - that's forced anyway.

Why this wins:

Every turn the opponent is left in one of two losing positions:

A) n mod 4 == 1 and both players have an even number of sheets.

B) n mod 4 == 3 and both players have an odd number of sheets.

From these states the strategy described makes the following transitions:

A->even->even->A

A->odd->odd->B

B->even->even->B

B->odd->odd>A

Eventually they will be left with either:

Exactly 1 sheet and both players are even. They are forced to take the sheet and lose.

Exactly 3 sheets and both players are odd. If they take two sheets, you take 1 sheet and become even and win. If they take one sheet, you take one sheet and reach the case above.