Project Euler Forum

CLARIFY THE PROBLEM FOR THE CASE 3,10

Obviously, it's a winning configuration for the first player.
(S)he can win by taking 2*3 = 6 stones from the larger pile. That will leave 3,4 for the other player, which, as stated in the Problem 325 (View Problem) is a losing configuration for the player whose turn is to play.

None of the solutions in the private forum made any special use of 7^10 which is used for modulo, so I am wondering how these modulos are decided. If there is no real benefit (I am not aware of any), then why not keep it to 10^n so that it makes it a little easy to debug? I tried to port my code to C++ and gave up because of overflows.

If answering this reveals any insights to this problem, please PM me. I don't want to waste a few posts in private forum to get this clarified.

There's nothing special to the modulus.
Initially we had chosen 7^11=1977326743 as modulus, but thought it might be a little bit too high.
So we've chosen 7^10=282475249.
Note that 10^8<7^10<10^9.
So if we'd chosen 10^9 as modulus I'm afraid your problems would have been the same.

why the player cannot take 1*3=3 stones or 3*3=9 stones leaving the configuration as 3,7 and 3,1.

The player can, but s/he would lose if s/he did.

If the configuration is (3,7): the second player will remove 1*3 leaving the configuration as (3,4) which is a losing position (as said above).

Also the configuration (3,1)=(1,3) is losing because the second player can simply remove all 1*3 coins.

The best strategy is to remove 2*3 = 6, leaving (3,4).

Hello,
an academic question: the configuration (1,1) is reachable from (1,2). in configuration (1,1) there is no larger pile anymore . is this a draw or a winning configuration? same for configuration (n,n), reachable from (n,k*n), n,k element N.

You're right; the problem statement doesn't actually define what happens there, but the (reasonably) obvious applies - you can treat either pile as the 'larger' pile, and thus remove all the stones and win.