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
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");
}
}
Solution
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow