You are not logged in. Please login at www.codechef.com to post your questions!

×

number game revisited NUMGAME2

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..

asked 31 Jan '15, 10:41

keshav_1994's gravatar image

0★keshav_1994
115
accept rate: 0%


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 :P 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.

link

answered 31 Jan '15, 20:43

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

edited 01 Feb '15, 11:33

Likely explained ( with recursion :P ).
Love it, +1.

(31 Jan '15, 20:51) mediocoder3★
1

@mediocoder Thanks, see the second explanation however, it's better and clean:P

(31 Jan '15, 21:07) damn_me3★

thanx ...it helped

(01 Feb '15, 09:39) keshav_19940★

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

(01 Feb '15, 09:43) keshav_19940★

I explained the induction hypothesis above in the answer. It's given in the editorial as well.

(01 Feb '15, 11:33) damn_me3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,126
×2,581
×294
×40
×17

question asked: 31 Jan '15, 10:41

question was seen: 5,608 times

last updated: 01 Feb '15, 11:33