Problem 859

[neilwheel]

In the problem description C(16)=64. The only way I have been able to reach this total is by excluding some starting pile configurations that only have odd size piles but still have a winning path for even.
eg 11,5

[mdean]

In the problem description C(16)=64. The only way I have been able to reach this total is by excluding some starting pile configurations that only have odd size piles but still have a winning path for even.
eg 11,5

I believe you have to assume both players play optimally. In that example you cited, if Odd chooses the stack of 11, Even loses.

[axby]

thank you all

[DJohn]

I think you are counting at least four games as wins for even, when odd can win. Remember, both players are trying to win, and both will look ahead to the end of the game to find their best option. If a player has a number of possible moves, and one of them leaves the other player with no way to win, that's the one they will choose.

(I say you're counting at least four games as wins for Even, because it's possible that there are some that you've counted as Odd wins that are actually Even. I stopped looking when I found one game in your list that is a win for Odd).

[axby]

thank you all

[mdean]

No, axby, I believe it's you that doesn't understand. In these types of problems, one player can always force a win. In your fourth case, Odd wins in one move. It is not counted.

[axby]

thank you all

[heteroing]

Either Odd is the winner or Even is the winner, there is no case where they both have a winning strategy since only one player wins. Maybe you're missing that Odd is always the first one to move in this game?

In any case, maybe you can explain how Even will ever win the game {13, 3}?
Odd, going first and having a functioning brain, will never play in the 13 pile allowing Even a move. Odd will choose to play in the 3 pile, reducing to {13, 1, 1} and winning as Even has no moves.

As mdean and DJohn have explained, each player moves only in their own interests. There is no reason for Odd to play {13, 3} -> {6, 6, 3} when the other available move wins instantly. Even is not in control of Odd's actions, and cannot rely on Odd making a mistake.

[yoni83]

Instead of arguing with people who have already solved the problem and understand what is being asked in it, I suggest that you learn some of the basic concepts in game theory. Here is a good starting point if you want to know what is meant by a "winning strategy": https://en.wikipedia.org/wiki/Zermelo%2 ... me_theory).

[DJohn]

I'm not going to provide partial answers or hints. What I will do is attempt to clarify what the problem statement means. And yes, this does belong in the "Clarifications on Project Euler Problems" forum.

It does not prohibit that Odd also has a winning strategy for the same series of numbers whose sum is 16

doesn't make sense, and suggests that you are misunderstanding what a "winning strategy" is (your use of "CQFD" makes me think your first language is French, and that this is a language issue). Each player is playing independently, and each player is trying to win. We say that Even has a winning strategy if Even is able to win regardless of what Odd does.

Let's say the game is not the one in the problem, but the classic Nim. In this example, there are three piles containing 1, 1, and 2 tokens to keep it simple. The players take turns, removing any number (greater than zero) of tokens from any one of the piles. If a player can't move, they lose. I'll call the players Odd and Even.

Odd can take one token from the first pile, one from the second pile, or one or two from the third pile. That's four possible moves to choose from.

If Odd wasn't very clever, they might choose to remove one token from the first pile. That leaves piles of 1 and 2. Even (who is clever) takes one from the second of these piles, leaving piles of 1 and 1. Odd takes one tile from one of them, then Even takes one tile from the other and wins because Odd has no possible move.

But because Odd is clever, they're not going to let that happen. They will instead choose to remove two tokens from the third pile, leaving two piles of 1 and 1 tokens. Even has to take one token from one of the piles. It doesn't matter which, because both choices lead to a single pile of one token. Odd then takes that one token, leaving nothing for Even. Odd has won.

That's what it means to have a winning strategy. Odd is able to win no matter what Even does, so Odd has a winning strategy and Even does not. If that's not the case - if Even is able to win no matter what Odd does - then we say that Even has the winning strategy.

It doesn't matter that Odd is able to play badly and lose, because we assume that the players are mathematicians and perfectly logical. They don't make mistakes. Odd won't make that bad move.

I can't work out what you think a strategy is. My best guess is that you might be interpreting it as a sequence of moves that ignores one player's desire to win. That's not what it means, and that's not how games work.

I recommend "Winning Ways for Your Mathematical Plays" by Berlekamp, Guy, and Conway if you want to learn about this kind of mathematical game. It's a fascinating subject.

[axby]

Either Odd is the winner or Even is the winner, there is no case where they both have a winning strategy since only one player wins. Maybe you're missing that Odd is always the first one to move in this game?

In any case, maybe you can explain how Even will ever win the game {13, 3}?
Odd, going first and
, will never play in the 13 pile allowing Even a move. Odd will choose to play in the 3 pile, reducing to {13, 1, 1} and winning as Even has no moves.

As mdean and DJohn have explained, each player moves only in their own interests. There is no reason for Odd to play {13, 3} -> {6, 6, 3} when the other available move wins instantly. Even is not in control of Odd's actions, and cannot rely on Odd making a mistake.

If Odd can choose any pile with an odd number of cookies, why wouldn't he choose 13 first? How do we know he actually has a functioning brain?
since the terms don't specify, I considered the choices favoring Even instead.
Now, assuming that Even and Odd have functioning brains, the result is indeed 64 and the list is:

{{16}, {14, 2}, {14, 1, 1}, {13, 2, 1}, {12, 4}, {12, 2, 2}, {12, 2,
1, 1}, {11, 2, 2, 1}, {10, 6}, {10, 5, 1}, {10, 4, 2}, {10, 2, 2,
2}, {10, 2, 2, 1, 1}, {9, 6, 1}, {9, 5, 2}, {9, 2, 2, 2, 1}, {8,
8}, {8, 6, 2}, {8, 6, 1, 1}, {8, 5, 2, 1}, {8, 4, 4}, {8, 4, 2,
2}, {8, 2, 2, 2, 2}, {8, 2, 2, 2, 1, 1}, {6, 6, 4}, {6, 6, 3,
1}, {6, 6, 2, 2}, {6, 6, 2, 1, 1}, {6, 6, 1, 1, 1, 1}, {6, 5,
5}, {6, 5, 4, 1}, {6, 5, 3, 2}, {6, 5, 2, 2, 1}, {6, 5, 2, 1, 1,
1}, {6, 4, 4, 2}, {6, 4, 4, 1, 1}, {6, 4, 3, 2, 1}, {6, 4, 2, 2,
2}, {6, 4, 2, 2, 1, 1}, {6, 4, 2, 1, 1, 1, 1}, {6, 3, 2, 2, 2,
1}, {6, 2, 2, 2, 2, 2}, {6, 2, 2, 2, 2, 1, 1}, {6, 2, 2, 2, 1, 1, 1,
1}, {5, 5, 4, 2}, {5, 5, 2, 2, 2}, {5, 5, 2, 2, 1, 1}, {5, 4, 4, 2,
1}, {5, 4, 2, 2, 2, 1}, {5, 3, 2, 2, 2, 2}, {5, 2, 2, 2, 2, 2,
1}, {5, 2, 2, 2, 2, 1, 1, 1}, {4, 4, 4, 4}, {4, 4, 4, 2, 2}, {4, 4,
2, 2, 2, 2}, {4, 4, 2, 2, 2, 1, 1}, {4, 3, 2, 2, 2, 2, 1}, {4, 2, 2,
2, 2, 2, 2}, {4, 2, 2, 2, 2, 2, 1, 1}, {4, 2, 2, 2, 2, 1, 1, 1,
1}, {3, 2, 2, 2, 2, 2, 2, 1}, {2, 2, 2, 2, 2, 2, 2, 2}, {2, 2, 2, 2,
2, 2, 2, 1, 1}, {2, 2, 2, 2, 2, 2, 1, 1, 1, 1}}.
thank you all

[heteroing]

We can assume this based on the term "winning strategy", meaning the player has a plan for what to do no matter what their opponent does. Good job matching the test case!