Understanding this solution to a puzzle

Question

I was doing a puzzle in a coding competition, and I'm stuck on one question. Basically I don't understand how can someone reach this solution. The puzzle was

Alice and Bob play the following game. They choose a number N to play with. The rules are as follows:

Bob plays first and the two players alternate.
In his/her turn, a player can subtract from N any prime number (including 1) less than N. The number thus obtained is the new N.
The person who cannot make a move in his/her turn loses the game.

Assuming both play optimally, who wins the game?

And the given solution is

int main() {
  long int T, N;
  for(scanf("%ld", &T); T > 0; T--) {
    scanf("%ld", &N);
    if (N % 4 == 1) {
      printf("ALICE wins\n");
    } else {
      printf("BOB wins\n");
    }
}

What competition? Is it still on-going? It will be highly unethical to ask how to solve problems from a competition if it is still ongoing (as it is unfair for those who actually try to solve it according to the rules - by their own) — amit
I am glad to hear. You should also link to the specific question. — amit
It's probably not your phrasing, but I despise "a player can subtract from N any prime number (including 1) less than N." 1 isn't prime! — Joshua Green

Daniel Fischer Daniel Fischer · Accepted Answer · 2012-11-11T16:07:19

It's sort of a Nim game. The player who finally faces N = 1 loses. If N % 4 != 1, Bob can take 1, 2 or 3 to make the next N ≡ 1 (mod 4), leaving Alice in a losing position. Otherwise, if N ≡ 1 (mod 4) at the start, Alice can counter Bob's move to leave a number ≡ 1 (mod 4) for Bob again.

Understanding this solution to a puzzle

1 Answers