Problem 260

[OscarPhilips]

As I understand it; The Stone Game (Problem 260 (View Problem)) is played with three piles of stones and two players, where the winning strategy is to take the last stone(s) from the board.

• • The board has three piles of stones;
  • At each player's turn, the player removes one or more stones from from one or more piles;
  • If the player takes stones from more than one pile, the player must remove the same number of stones from each of the selected piles;
  • The player taking the last stone(s) wins the game.

In other words, the player chooses some N>0 and removes:

• • N stones from any single pile; or
  • N stones from each of any two piles (2N total); or
  • N stones from each of the three piles (3N total).

A winning configuration is one where the first player can win, taking all the remaing stone(s) on the board; and a losing configuration is one where the second player can force a win, no matter what the first player does.

Project Euler gives the following as examples of losing configurations:
(0,1,2) and (1,3,3)

I do not have an issue with the first of these losing configuration examples, as I understand that (0,0,2), (0,1,1) and (0,1,0) would be winning cofigurations, allowing the next player to remove all of the ramaining stones, but I cannot see how (1,3,3) is considered a loosing configuration, where regardless of the legal move taken by the next player, that player's opponent can immeditely win (as is implied by the problem statement) ... by selecting one stone from pile as clearly (1,2,3), (1,1,3), and (1,2,2) could be the left after this next turn, none of which allow for an immediate win.

[genious999]

by selecting one stone from pile as clearly (1,2,3), (1,1,3), and (1,2,2) could be the left after this next turn, none of which allow for an immediate win.

For all three of those, the player can take stones leaving (0,1,2) which is a losing position, making each a winning position. It might help to say that a winning configuration is a configuration where the player can make a move that either wins the game or leave the second player with a losing configuration.

[harryh]

I cannot see how (1,3,3) is considered a loosing configuration, where regardless of the legal move taken by the next player, that player's opponent can immeditely win (as is implied by the problem statement) ...

No, the problem statement does not imply that the "player's opponent can immediately win".
It clearly states: "losing configurations: any legal move leaves a winning configuration for the second player" and
a "winning configuration" is previously defined as "one where the first player can force a win".

"Forcing a win" is not the same as an "immediate win", since a player can "force a win" by following a strategy which needs several moves.

E.g. The configuration (1, 2, 3) is a winning configuration, since the first player (A) can remove the three stones of the third pile, leaving for the second player (B) the configuration (1, 2, 0). Then, no matter what player B does, player A can take all the remaining stones at his next turn.

[pgrontas]

Hello. It seems that I cannot understand this problem.

I have the following question: Why is 1,3,3 a losing configuration;

player A: 1,3,3 Pick N=1 remove (0,1,1)
player B: 1,2,2 Pick N=1 remove (0,1,1)
player A: 1,1,1 wins.

I must have a terrible misunderstanding. Can somebody clarify this?
Thanks in advance.

[stijn263]

You say:
player A: 1,3,3 Pick N=1 remove (0,1,1)

Now player B can remove (1,1,0):
player B: 1,2,2 Pick N=1 remove (1,1,0)

And then player A is left with 0,1,2 and that is a losing configuration.

Try to assume player A and B are infinitely smart. Then in some situations player A wins (a winning configuration) and in some situations player B wins (a losing configuration). I hope it's clear now, and if not, feel free to ask good luck!

[pgrontas]

Thank you.
I will give it a shot.

[LarryBlake]

I'm curious about the wording of this problem. What does the subscript i refer to in x_i, y_i, z_i ? Does it mean "Integer"? (It's not keeping me from doing the problem, just wondering.)

[harryh]

i is the index of the loosing configuration(s).
E.g. if (0,1,2) and (1,3,3) are the only losing configurations you need to consider, then you can assing the index i=1 to (0,1,2) and the index i=2 to (1,3,3). (The actual order is of course unimportant).

Then, x₁=0, y₁=1, z₁=2,
x₂=1, y₂=3, z₂=3

The sum [sum](x_i+y_i+z_i) runs over the possible values of the index i, but specific limits (e.g. for i=1 to 1000) are not needed, since we are told that

(x_i,y_i,z_i) ranges over the losing configurations.

[Ooki]

Hey
After struggling with this problem for a while I wondered about 2 things:
1) Should I consider (2,1,0) (2,0,1) as a valid configuration(s)? Or only the permutation (0,1,2)

2) Could anyone give me the loosing configurations up to z <= 10 or so?
(Or at least give me the sum, for a slightly lower number than z =< 100)

[thundre]

Hey
After struggling with this problem for a while I wondered about 2 things:
1) Should I consider (2,1,0) (2,0,1) as a valid configuration(s)? Or only the permutation (0,1,2)

2) Could anyone give me the loosing configurations up to z <= 10 or so?
(Or at least give me the sum, for a slightly lower number than z =< 100)

1. Only one permutation satisfies x ≤ y ≤ z ≤ 1000.

2. The sum through 10 is 213.