What does the editorial for NUMGAME2 explain?

Can someone provide a more explanatory description for NUMGAME2 Editorial.

https://discuss.codechef.com/questions/4162/numgame2-editorial

Call N a losing number if the next player to play can be forced to lose by the other player. Any number which is not a losing number we will call a “not losing number”. (Perhaps we should call it a winning number.)

The idea is that every possible play from a losing number will leave a not losing number. And that there is at least one possible play from every not losing number that leaves a losing number.

Let’s calculate whether the first few integers are losing numbers or not losing numbers…

1 is a losing number, because no moves are possible.

2 is not a losing number, because a play of subtracting 1 leaves 1, which is a losing number.

3 is not a losing number, because a play of subtracting 2 leaves 1, which is a losing number.

4 is not a losing number, because a play of subtracting 3 leaves 1, which is a losing number.

5 is a losing number, because the possible plays are subtracting 1, 2 or 3, leaving 4, 3 or 2, all of which are not losing numbers.

6 is not a losing number, because a play of subtracting 1 leaves 5, which is a losing number.

7 is not a losing number, because a play of subtracting 2 leaves 5, which is a losing number.

8 is not a losing number, because a play of subtracting 3 leaves 5, which is a losing number.

9 is a losing number, because the possible plays are 1,2,3,5 or 7, leaving 8,7,6,4 or 2, all of which are not losing numbers.

The pattern should be clear. A proper proof needs an induction argument. One of the comments to the editorial gives a formal proof by induction. I will sketch the argument here.

The induction hypothesis is that numbers N of the form N=4x+1 are losing numbers.

There are two things to prove:

  1. that there is a valid play from any not losing number that produces a losing number.
  2. that any play from a losing number produces a not losing number

If N is not a losing number, then by our hypothesis N is not of the form 4x+1. So N must be one of the forms 4x+2, 4x+3, or 4x+4. So a play of subtracting 1, 2 or 3 will reduce N to 4x+1, which is a losing number.

If N is a losing number, then by our hypothesis it has form 4x+1. Then because there are no primes that are multiples of 4, then for any prime p we find that 4x+1-p \ne 4y+1, so all plays produce not losing numbers.

3 Likes

I really want to upvote this answer . :slight_smile:

This gives all the explanation I needed. Thanks.

@vijju123 @admin can you make this the official editorial of NUMGAME2

According to me in case N=3, there are 2 possibilities:
a) B: 3-1 = 2 ;; A: 2-1 = 1 —> Bob cant make a move so Alice wins.
b) B: 3-2 = 1 —> Alice cant make a move. Bob wins.

So 3 can be a losing no. depending upon what Bob chooses. Isn’t is so? Kindly correct me if I misunderstood the logic.