Problem 391

[akbaraka]

I'm not sure I understand the problem.

Can each number [1..n] used at most ONCE during the game?

Let n = 5. c starts at 0.
Player 1 chooses 4, so c becomes 0 + 4 = 4.
Player 2 chooses 5, so c becomes 4 + 5 = 9.
Player 1 chooses 3, so c becomes 9 + 3 = 12.
etc.

Can anyone continue the game until it end, please?

[mdean]

Since c increases each turn, it's not possible for c to have the same value twice during the same game.

[jaap]

Can each number [1..n] used at most ONCE during the game?

No, they can be used any number of times. The only restriction is that the new value of c must be one of the members of the set S.
If you examine the sequence of numbers in S more closely you will find that as you go further you go, larger gaps will start to appear occasionally. Eventually there will be a gap larger than n so that no more move is possible.

[rockstome]

Can I pm someone my results for M(i), 0<=i<=10?

[Marcus_Andrews]

I could be wrong, but I think the general consensus is that result-confirmation is best withheld until at least 50 people have solved the problem (especially since Problem 391 is only a few hours shy of being a week old). I know hk has said this before when it's come to public confirmation, but I'm not sure if that also extends to PMs. If it's cool with hk, then feel free to PM me.

Otherwise, I'd recommend verifying your results via brute force for low values of n. If you think your answer for M(n) is correct, try playing a few games with that assumption.

[hk]

In my (personal) opinion (partial) answer confirmations should not be given for problems that are still under competition in whatever way because it disturbs said competition.
In my opinion confirmations by PM disturb it even more.
If one wants to go for the most recent problem(s) one should be prepared to face the full weight of unaided solving.

[iordan_tanev]

Hi,
I have a little problem understanding the problem. If c starts at 0 and player can chose to add number from 1 to n how can M(2) be 2.if n is 2 and first player chose 2 the the second player can olso schose 2 becouse 4 is in S. So if first player choses 2 for n=2 second player still has a valid move. Myabe i missunderstood something if some one can explain to me how the values given in the example are found.M(2), M(7), M(20)
Best Regards,
Iordan Tanev

[TripleM]

'Force a win' doesn't mean you have to win on your very first turn - it means that no matter how the second player decides to play on any of their moves, the first player can always make moves that result in a win by the time the game finishes.

In this case: after the first player chooses 2, the second player must choose 2. The first player now chooses 1; the second player must choose 2; the first player chooses 2 and wins. There was nothing the second player could do to ensure they won instead - so the first player could force a win. In larger cases, the second player may have a choice of moves at various stages - but if they can't *ensure* they win no matter what, then that's a still a forced win for the first player.

[jaap]

Hi,
I have a little problem understanding the problem. If c starts at 0 and player can chose to add number from 1 to n how can M(2) be 2.if n is 2 and first player chose 2 the the second player can olso schose 2 becouse 4 is in S. So if first player choses 2 for n=2 second player still has a valid move. Myabe i missunderstood something if some one can explain to me how the values given in the example are found.M(2), M(7), M(20)
Best Regards,
Iordan Tanev

Remember that M is it is the highest first move for the first player that will eventually win the game for him regardless of what choices the second player makes.

For example n=2:
If the first player chooses 2 as his first move, then all the next moves are forced until eventually the first player makes c=9. The second player now has no moves left (c=12 is not reachable) so loses, making the first player the winner. Therefore the highest first move for the first player that will eventually win the game for him is 2, so M=2. The second player didn't have any choice at all in this game, but for larger n he does and it gets much more complicated to show that the first player will always be able to win.

[Marcus_Andrews]

I think it's important to point out that simply picking the right "first move" doesn't mean you're automatically going to win no matter what moves are done from that point forward by either side. M(2) just so happens to work out that way and so I don't think it's necessarily the best example. I know jaap touched on this but I just wanted to echo it for emphasis.

Consider that M(20) = 4. It is still possible that you can choose 4 as your first move and lose if you choose the wrong numbers later on. You still have to play correctly. M(n) just tells you the highest number that you can choose on your first turn that is part of a winning strategy. In other words, if you were to play the n=20 game and select any valid move higher than 4 from [5, 7, 9, 12, 13, 15, 17, 20] on your first turn, you cannot guarantee that you win, but you *can* if you choose 4 as your first move.

[mkader]

"Let M(n) be the highest number the first player can choose at her first turn to force a win," can anybody explain what is win?
M(2) = 2, M(7) = 1 and M(20) = 4

[Marcus_Andrews]

You win the game when your opponent has no valid moves left. M(n) is the highest possible value of the first move that is part of a winning strategy, which means you can win no matter what the opponent does.

[thundre]

"Let M(n) be the highest number the first player can choose at her first turn to force a win," can anybody explain what is win?
M(2) = 2, M(7) = 1 and M(20) = 4

To elaborate on what Marcus said, here's a concrete example for n=2.
S = {0, 1, 2, 4, 5, 7, 9, 12, ...}
Player 1 chooses 2.
Player 2 must choose 4.
Player 1 must choose 5.
Player 2 must choose 7.
Player 1 must choose 9.
Player 2 cannot move, because 12-9 > n, so player 1 wins.

It's easy to see that if player 1 had chosen 1, player 2 would take 2 and the result would be reversed, with player 1 unable to move.

Since c=2 is a win for the player who chooses it in the n=2 game, M(2) = 2.

[pll]

Can someone who’s solved the problem confirm that the given values M(20) = 4 and sum_1^20 M(n)^3 = 8150 are correct?

I have an analysis of the game which seems watertight, and agrees with the smaller values of M given in the question, but disagrees with the given values of M(20) and the small sum of cubes. I presume I’ve most likely made a mistake somewhere, but just wanted to check.

[TripleM]

Yes, they're correct.

[rockstome]

sum_1^10 M(n)^3 = 683?

[thundre]

sum_1^10 M(n)^3 = 683?

That is correct.

[rockstome]

only one more and I probably give up on this one...
sum_1^13 M(n)^3 = 3287 ?

[sivakd]

It should be possible to bruit-force and confirm these easily. With 12 GB RAM I can go all the way up to n = 1 to 31.

[rockstome]

ok, i brute force and it's correct
but i can't find any pattern