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

×

NUMGAME2 - Editorial

-7
4

PROBLEM LINKS

Practice
Contest

DIFFICULTY

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

admin's gravatar image

0★admin ♦♦
19.7k350498541
accept rate: 35%

17

Is this seriously meant to be an editorial ?

(25 Mar '14, 15:19) dpraveen ♦♦4★

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?

link

answered 25 Mar '14, 14:46

cool_techie's gravatar image

2★cool_techie
28971218
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) priyankpalod4★

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.

link

answered 22 Aug '14, 21:47

ironmandhruv's gravatar image

4★ironmandhruv
333239
accept rate: 20%

I am getting WA for this code. What can possibly be wrong (unless there is a bug somewhere)! http://www.codechef.com/viewsolution/3799416

link

answered 29 Apr '14, 00:25

shivee1701's gravatar image

2★shivee1701
26112
accept rate: 0%

edited 29 Apr '14, 00:30

@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

link

answered 23 Jan '15, 12:26

eknoor292's gravatar image

4★eknoor292
2233
accept rate: 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)?

link

answered 27 May '17, 04:56

jahidshohel's gravatar image

0★jahidshohel
2
accept rate: 0%

Can someone tell me why if n%4==1 then Alice wins? And why not if n%2==1 then Alice wins.

link

answered 23 Jun '17, 14:13

goyalpradhuman's gravatar image

4★goyalpradhuman
1
accept rate: 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!

link

answered 18 Jul '17, 18:15

naruto323's gravatar image

1★naruto323
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) shubham633★

How does Bob win when N=7 ?

link

answered 12 Sep '17, 20:26

shivan111's gravatar image

2★shivan111
101
accept rate: 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... :)

link

answered 17 Dec '17, 17:53

rom1n's gravatar image

2★rom1n
1
accept rate: 0%

I can't believe a mathematical puzzle has literally no description or explanation for an editorial. What even is this.

link

answered 27 Aug '18, 20:41

ankitmaity's gravatar image

2★ankitmaity
254
accept rate: 0%

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,490
×3,706
×17
×15

question asked: 26 Nov '12, 17:24

question was seen: 8,793 times

last updated: 27 Aug '18, 20:41