NUMGAME2 - Editorial

editorial
, , ,
1

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.

3 Likes
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?

1 Like
3

Is this seriously meant to be an editorial ?

15 Likes
4

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

5

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

1 Like
6

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.

7

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

@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

9

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)?

10

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

11

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!

12

How does Bob win when N=7 ?

13

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… :slight_smile:

14

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

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