PROBLEM LINKSDIFFICULTYEASY EXPLANATIONFor this particular combinatorial game theory problem the the values of N for which the first player looses are 1,5,9,13,17,21,25 etc. SETTER'S SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 26 Nov '12, 17:24

I have written a basic brute force algorithm to check the winning positions using the N,P positions. The game is equivalently the subtraction game with set S={1,2,3} and the rest of the primes are irrelevant. For a subtraction game(refer to wikipedia) any position with n%(k+1)==1 is a losing position for the current player. Given that any other number than can be subtracted are primes and all primes are of the form 4n1 and 4n+1 they can be equivalently replaced by 3 and 1. Consider total pile to be 8: Two possible ways are 8>1 (Bob cannot make a move) Subtracting a prime 7(of the form 4n1) is equivalently replaced by 3. A total pile of 5 can be given to Bob and since N%4==1 for 5, it is a losing position for Bob. 8>5>4>1 8>5>3>1 8>5>2>1 Hence, any move made by Bob from 5(a losing position) results in him losing. answered 22 Aug '14, 21:47

I am getting WA for this code. What can possibly be wrong (unless there is a bug somewhere)! http://www.codechef.com/viewsolution/3799416 answered 29 Apr '14, 00:25

@shvee1701 The fast i/o in your code seems to be the problem. here's a code that i modified and submitted http://www.codechef.com/viewsolution/5967564 answered 23 Jan '15, 12:26

Can someone tell me why if n%4==1 then Alice wins? And why not if n%2==1 then Alice wins (of course except when n=1)? answered 27 May '17, 04:56

Can someone tell me why if n%4==1 then Alice wins? And why not if n%2==1 then Alice wins. answered 23 Jun '17, 14:13

At n=7 BOB CAN CHOOSE : 2 HENCE N = 72 = 5. NOW NO MATTER WHAT ALICE CHOOSES (E.G. 1, 2, OR 3) SHE WILL LOSE.. IF SHE CHOOSES 1 : 5  1 = 4 THEN BOB WILL CHOOSE 3 >>>> RESULT BOB WINS  IF SHE CHOOSES 2 : 5  2 = 3 THEN BOB WILL CHOOSE 2 >>>> RESULT BOB WINS  IF SHE CHOOSES 3 : 5  3 = 2 THEN BOB WILL CHOOSE 1 >>>> RESULT BOB WINS HENCE NO MATTER WHAT ALICE CHOOSES.. IT WILL BE INSTANT DEATH FOR HER... :) answered 17 Dec '17, 17:53

I can't believe a mathematical puzzle has literally no description or explanation for an editorial. What even is this. answered 27 Aug '18, 20:41

Is this seriously meant to be an editorial ?