Problem 260

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
OscarPhilips
Posts: 1
Joined: Thu Jan 15, 2009 4:56 am

Problem 260

Post by 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
Posts: 53
Joined: Mon Oct 20, 2008 10:48 pm

Re: Problem 260

Post by genious999 »

OscarPhilips wrote: 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
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 260

Post by harryh »

OscarPhilips wrote: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
Posts: 6
Joined: Sun Jun 22, 2008 8:10 pm

Re: Problem 260

Post by 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.

User avatar
stijn263
Posts: 1505
Joined: Sat Sep 15, 2007 11:57 pm
Location: Netherlands

Re: Problem 260

Post by 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
Posts: 6
Joined: Sun Jun 22, 2008 8:10 pm

Re: Problem 260

Post by pgrontas »

Thank you.
I will give it a shot.

LarryBlake
Posts: 100
Joined: Sat Aug 29, 2009 8:49 pm

Re: Problem 260

Post by LarryBlake »

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

harryh
Posts: 2091
Joined: Tue Aug 22, 2006 9:33 pm
Location: Thessaloniki, Greece

Re: Problem 260

Post by 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, x1=0, y1=1, z1=2,
x2=1, y2=3, z2=3

The sum [sum](xi+yi+zi) 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
(xi,yi,zi) ranges over the losing configurations.

Ooki
Posts: 4
Joined: Thu Mar 29, 2012 3:02 pm
Location: Norway

Re: Problem 260

Post by 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
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 260

Post by thundre »

Ooki wrote: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.
Image

Post Reply