NUMGAME2 - Editorial

editorial
, , ,
23

2.In his/her turn ,a player can subtract from N any prime number(including 1) less than N.
“Any prime number.”

24

if N = 21 than if in the first play,
1st player (21-17) =4
2nd player (4-2)=2
1st player (2-2) = 0 than the first player wins the game but in solution first player loses on 21

26

can someone explain this: if N = 15 and bob choose 13 in his first turn, and Alice then chooses 1, Bob will lose, but according to the explanation he will win. How?

27

Here is how I got the answer:

  1. FACT: If on your turn the number is n, and n-1 is prime, you win.
    You just need to substruct n-1 from n and it will be 1, so enemy loses.
    So you don’t want your enemy get such number n that n-1 is prime.
  2. FACT: In your turn you should make n%2==1. (Except for 3, mentioned below).
    That’s because prime%2==1 (except for 2), so n-1 will only be prime if n==3.
    Except for 3. ! You don’t want to obtain 3 after your turn (because enemy will substract 2 from 3 and you are done for)
  3. FACT: If n%4!=1 you can always obtain n%4==1 after your turn:
    If n%4==0: n->(n-3), (n-3)%4==1;
    If n%4==2: n->(n-1), (n-1)%4==1;
    If n%4==3: n->(n-2), (n-2)%4==1;
    BUT if n%4==1: to get n%4==1 you have to substract n%4==0; but it’s not a prime!
    As you can see 3%4==3 so if you can always obtain n%4==1 after your turn, you win.
    So if n%4==1 → Bob CANNOT obtain n%4==1 but Alice always can obtain n%4==1 and wins.
    If n%4!=1 Bob obtains n%4==1 with first turn and Alice can’t obtain n%4==1 so Bob wins.