Can someone provide a more explanatory description for NUMGAME2 Editorial.

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

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:

- that there is a valid play from any not losing number that produces a losing number.
- 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 e 4y+1, so all plays produce not losing numbers.