Problem 882

[FransM]

I've been struggling with 882 for quite a while.
Seeing that there are not that many people who solved it yet, and thinking that the issue is with some of the higher values I want to suggest to give one or two additional data points e.g. S(100)

[ksaho]

I seem to have contradicted the result for S(2), so it is possible that I may have misunderstood something.

I am doing S(2) by hand and came across a series of moves that will have Player 0 win with only a single skip.

Choosing a number is equivalent to choosing an index:

Code: Select all

Trn   Plyr	Idx	1	2	2
1	1	0	0	2	2
2	0	2	0	2	1
3	1	2	0	2	0
4	0	1	0	1	0
5	1	1	0	0	0
6	0	-1	-	-	-
7	1	1	Player 1 Loses

I have either clearly misunderstood something about the question, or the minimum number of skips for S(2) = 1.

[heteroing]

For S(2), player one will not choose to take the bit off the 1, and will instead take the bit off the 2 reducing to [1, 0, 2] as shown in the problem's stated example. Player zero is forced to take the 0 from the remaining 2, player one is forced to take a 1, player zero now has no moves and must use a skip, player one will again take a 1, and player zero again is forced to use a skip (at which point player zero wins).

[ksaho]

If I am reading things correctly, the examples given for S(n) are just examples that we could get for some games, not the absolute best values of S(n)?

[heteroing]

In this case it is an optimally played game for both players. Player one will choose whatever move requires player zero to use the maximal number of skips, and player zero will choose whatever move allows player one to force as few skips as possible. The values of $S(n)$ given are such that, for the game corresponding to $n$, if player zero is allowed fewer than $S(n)$ skips, player one has a winning strategy, and if player zero has at least $S(n)$ skips, player zero always wins.

For S(2), if player zero has only one skip, then player one can choose the move given in the example to win the game, so player zero will not have a winning strategy. If player zero has two skips, you will find that no matter what player one chooses to play, he will run out of moves before player zero does.

[ksaho]

I think I understand now. I have been generating move lists randomly to get the indices played for the respective players, and not playing the game in an adversarial manner from each player's perspective.

Thank you for clarifying this.