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

×

EASY

# EXPLANATION

For 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 SOLUTION

Can be found here.

# TESTER'S SOLUTION

Can be found here.

This question is marked "community wiki".

asked 26 Nov '12, 17:24

19.8k350498541
accept rate: 36%

17

Is this seriously meant to be an editorial ?

(25 Mar '14, 15:19)

 2 The solution of the problem is that if the n%4==1 then ALICE wins else BOB wins. Can anyone please explain how to approach these kind of problems. That is how to figure out this trick? answered 25 Mar '14, 14:46 289●7●12●18 accept rate: 22% 1 if you see all prime numbers except for 2 ,all others fit in either 4n-1 or 4n+1 where n is a positive integer (30 Apr '14, 05:19) chiragjn5★ 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 :True for p=0. step:let 1) 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. (01 Oct '14, 02:34)
 1 http://ideone.com/fHC7w8 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 4n-1 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 4n-1) 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 333●2●3●9 accept rate: 20%
 0 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 26●1●1●2 accept rate: 0%
 0 @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 223●3 accept rate: 0%
 0 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 2 accept rate: 0%
 0 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 1 accept rate: 0%
 0 The editorial is quite ambiguous lets take a case where the value of N is 13 B chooses: 7 13-7=6; C chooses: 3 6-3=3; B chooses : 2 3-2=1; now Alice can't make a move so Bob wins r8? then how come those prescribed values are meant to looses ? Explain me if i am wrong! answered 18 Jul '17, 18:15 2 accept rate: 0% If N=13 and Bob choses 7, then Alice is left with 6. She takes 1 leaving 5. Bob can take 1, 2 or 3. If Bob chooses 1, Alice is left with 4. She takes 3 and wins as Bob cannot choose the remaining 1. If Bob chooses 2, Alice is left with 3. She takes 2 and wins. If Bob chooses 3, Alice is left with 2. She takes 1 and wins. (14 Feb '18, 22:51)
 0 How does Bob win when N=7 ? answered 12 Sep '17, 20:26 10●1 accept rate: 0%
 0 At n=7 BOB CAN CHOOSE : 2 HENCE N = 7-2 = 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 2★rom1n 1 accept rate: 0%
 0 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 25●4 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,852
×3,820
×17
×15

question asked: 26 Nov '12, 17:24

question was seen: 9,128 times

last updated: 27 Aug '18, 20:41