for test case 100 and 101 nearest prime no. is 97 now n will be 3 and 4, nearest prime no will be 2 and 3 so now botth n will be 1 and alice will win in both cases but using condition n%4==1 alice wins only in 101 not in 100 please someone explain…
I misunderstood the question at once, but here is the case how Bob can win when n=100.
Lets say Bob picks 97, then alice can pick either 1 or 2. If alice picks 2, Bob will not be able to make the move further and will not win. Since, he plays optimally, he’ll not pick 97(change the first move). Lets say he picked 89 in his first move. Alice can pick from n=11, numbers 7,5,3,2,1. Lets say Alice picked 7. Bob is left with 4, he’ll pick 3 and Alice left with 1, Bob wins. Since Alice plays optimally, she’ll not pick 7. Lets say she picked 5, then bob left with 6, he picks 5 and alice left with 1. Bob wins here also, thus Alice changes her second step. He choses 3. Now, Bob left with 8 and picks 7 and we are on the same state again.
Omg… alice thinks so much 
Lets say Alice picked 2 now, Bob is left with 9, and Bob can now pick, (7,5,3,2,1). For values 7,5,3 Bob will lose, thus, he’ll go for 2. Alice is now left with 7. If alice picks 5 here, she loses and so on… it continues , recursively. You’ll get the solution I suppose when Alice picks 1 in her second move.
Also, its better too explain it this manner. We know for every n, if n%4==1, then the player who is not playing(whose turn is not) will win(Since bob plays the first and Alice wins if the conditions is true). Thus for n=100, if Bob picks 97 then we are left with n=(100-97)=3, currently It’s alice’s turn, thus condition is false and alice will win. So, we change first move to 89, Now it’s alice’s turn (100-89)=11. Condition is again false, we again change the move to n= (100-87)=13 and it’s alice’s turn. Thus, condition is true here and Bob wins.
Go by induction. hypothesis: Let for n=4p+1, Player whose chance isn’t now, wins. And for n=4p+2 or 4p+3 or 4p+4, Player having Chance is the winner.
Base Case i.e. true for p=0.
step 1) let n=4(p+1)+1 i.e. n=4p+5 Now bob will need to subtract something from it so that the resulting no. is of the form 4q+1. To do so, he will have to subtract some integer 4m which is not prime. Hence alice wins.
2) n=4(p+1)+2 or 4(p+1)+3 or 4(p+1)+4 i.e n=4p+6 or 4p+7 or 4p+8 respectively. So Bob will subtract 1 or 2 or 3 respectively to get 4p+5 on Alice’s turn.
Now same problem arises for Alice as Bob Hence Bob wins.
That’s why redeucing a problem to its subproblem is an optimal strategy. And whether the players are Bob and ALice, optimally playing depends on the current value of n, not on the player who’s turn it is. This is very similar to the famous subtraction game for primes(1,2,3). Rest of the primes are irrelevant.
5 Likes
Likely explained ( with recursion ).
Love it, +1.
thanx …it helped
but i wanna ask sumthing… that in this soln n%4==1 … we just searched for results 1- 20 nd generalized for all ‘n’…
Is it the right way ??? i mean for every n satisfying above condition , is it necessary that the player who is not playing will win ???
can’t there be a case when he couldn’t find any such prime number where he could win ??? there is no mathematical proof of the ans
I explained the induction hypothesis above in the answer. It’s given in the editorial as well.