# Understanding this solution to a puzzle

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:

1. Bob plays first and the two players alternate.
2. 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.
3. 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 Nov 11 '12 at 15:49
No no, its a practice question from codechef – neel Nov 11 '12 at 15:52
I am glad to hear. You should also link to the specific question. – amit Nov 11 '12 at 15:54
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 Nov 11 '12 at 16:10
– neel Nov 11 '12 at 16:56

## 1 Answer

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.

-
What to do if we dont subtract prime but the divisor of number – neel Nov 11 '12 at 16:17
That's far more complicated. I don't think there is an easy way to determine from which values the beginning player can force a win with that rule, but I haven't analysed that problem deeply so far. But it sounds interesting. – Daniel Fischer Nov 11 '12 at 16:21
Actually, @neel, scratch that, it is easy. If `N` is even, the beginning player can force a win (always taking 1). From an odd `N`, the beginning player loses. If `N` is odd, each divisor is also odd, then the next player has an even (winning) number left. – Daniel Fischer Nov 11 '12 at 16:27
thanks for your help – neel Nov 11 '12 at 16:34
@neel: On the "how can someone reach this solution" part of your question: "by working backwards", as illustrated in the answer. That is, these problems are often solved by finding a small case that is a win for one of the players, and then working backwards to see how a player can force that situation. – Patricia Shanahan Nov 11 '12 at 17:33
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://stackoverflow.com/questions/13332711/understanding-this-solution-to-a-puzzle", "fetch_time": 1448781980000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2015-48/segments/1448398456975.30/warc/CC-MAIN-20151124205416-00027-ip-10-71-132-137.ec2.internal.warc.gz", "warc_record_offset": 209457424, "warc_record_length": 18725, "token_count": 795, "char_count": 2788, "score": 3.6875, "int_score": 4, "crawl": "CC-MAIN-2015-48", "snapshot_type": "latest", "language": "en", "language_score": 0.9426011443138123, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00014-of-00064.parquet"}