Problem 366

[thundre]

This is the second week that the new problem has been unavailable for the first hour. DOS attack?

I have a question about the problem, though.

What is M(1)?

"The first player may remove any positive number of stones, but not the whole pile."

There is no legal move for the first player if you start with one stone. Is M=0 in that case?

[jaap]

There's a (repeated) spelling error in the problem - it should be "losing", not "loosing".

[hk]

There's a (repeated) spelling error in the problem - it should be "losing", not "loosing".

Thanks. Corrected.

[Marcus_Andrews]

thundre: M(1) = 0, for all intents and purposes; I think the problem description should be rephrased a bit to ask for 2<=n<=10^18 instead.

[sivakd]

While I had the same dilemma initially, IMHO, since the problem states "∑M(n) for n≤100 is 728. " shouldn't be too hard to figure what should be expected of M(1).

[hk]

How about:

Let M(n) be the maximum number of stones the first player can take from a winning position at his first turn and M(n)=0 for any other position.

?

[thundre]

How about:

Let M(n) be the maximum number of stones the first player can take from a winning position at his first turn and M(n)=0 for any other position.

?

I prefer Marcus' suggestion -- exclude n=1 from the summation domain by specifying 2 <= n <= 10¹⁸. That case makes no sense as a game, and I don't think it adds anything to the problem.

[hk]

In fact I don't see the need of any change in the wording at all.
If you look at this site: http://sps.nus.edu.sg/~limchuwe/cgt/cgt1.htm
you will see that positions that are not winning, are considered losing.
That also holds for positions where no legal move is possible.

[jaap]

In fact I don't see the need of any change in the wording at all.
If you look at this site: http://sps.nus.edu.sg/~limchuwe/cgt/cgt1.htm
you will see that positions that are not winning, are considered losing.
That also holds for positions where no legal move is possible.

But there the rules are that the first person who does not have a legal move available loses. In this problem it states that the person to take the last stone wins. These two definitions are only equivalent if there is always a legal move while there are still stones in the pile.

[Marcus_Andrews]

In fact I don't see the need of any change in the wording at all.
If you look at this site: http://sps.nus.edu.sg/~limchuwe/cgt/cgt1.htm
you will see that positions that are not winning, are considered losing.
That also holds for positions where no legal move is possible.

M(n)=0 is defined for a losing position if I am eventually going to lose. I can only lose if the opponent wins by taking the last stone. If a player can't even take a stone to begin with, how can we define who's won or lost? While it's not hard to figure out what the n=1 case should equate to for convenience, I feel it's still an exception-case that needs to be either explicitly defined for the sake of descriptive rigor, or excluded from the solution domain altogether.

[hk]

How about:

Let M(n) be the maximum number of stones the first player can take from a winning position at his first turn and M(n)=0 for any other position.

?

So why was this proposal discarded? It seems to fit all comments.
I do not like the proposal 2<=n<=10^18.

[Marcus_Andrews]

How about:

Let M(n) be the maximum number of stones the first player can take from a winning position at his first turn and M(n)=0 for any other position.

?

So why was this proposal discarded? It seems to fit all comments.
I do not like the proposal 2<=n<=10^18.

Given the nature of the problem, I think this proposal is fine, too.

[hk]

Made it that way.

[albert]

I have a small nit to pick about euler366.

Apparently a starting heap of one stone is valid.

Now the first player may only remove one stone, but not the whole pile, which is one
stone. So there is no move for the first player.
From the result 728 I conclude that M(1) = 0.

There are three kinds of positions, with a winning move, a move that leaves a winning
position and no move at all.

Only for the first category we are counting. I think that is a bit too clever.
Why not just leave a position with 1 stone out?

Groetjes Albert.

[Marcus_Andrews]

viewtopic.php?f=50&t=2740#p29571

[rayfil]

@ albert

Please try to post in existing topics related to specific problems. You can easily find them by searching for "Problem XXX", making sure to pad the problem number with leading 0's if it less than 100.

[mdean]

I haven't exactly been active with Project Euler lately, but I have a feeling this one's going to bug me for a while. I think I have the majority of cases figured out, but some I still have to do out individually at this point. Which probably wouldn't be a big issue if we were dealing with something smaller than a quintillion...

[cowmandude]

I think that I may have misunderstood the problem somehow.

The problem states: "...when n=17 the first player can remove one or four stones. "

I believe that taking 5 stones is a winning move for the first player as per my understanding of the problem. Would someone be willing to play through the game with me and show me where my flaw in understanding is?


Note: I assume that these very low values of n are acceptable to post in the forum. If I'm wrong please let me know!

[Marcus_Andrews]

To guarantee your winning position, 4 stones is the maximum amount you can remove when n=17.

[thundre]

The problem states: "...when n=17 the first player can remove one or four stones. "

I believe that taking 5 stones is a winning move for the first player

So you leave me 12 stones? I take 1.

Now there are 11 and you can take 1 or 2. Whichever you choose, I take the complement, bringing the pile down to 8, and depending how we got there, you are limited to either 2 or 4 stones.

If you take 3 or 4, I take the rest and win. If you take 1 or 2, I again take the complement, bringing the total down to 5.