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 \ne 4y+1, so all plays produce not losing numbers.
4 Likes
I really want to upvote this answer . 
This gives all the explanation I needed. Thanks.
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.