mathematics - The subtraction game

Alice and Bob play a game that starts by Bob picking a secret integer $N\ge100$. Then the game goes through several rounds.

• In every round, Alice picks an integer $x\ge3$. Every number can be picked at most once (and hence cannot be picked again in later rounds).


• Alice announces $x$ to Bob.


• If $x$ divides Bob's current secret value $N$, then Alice wins and the game ends.


• If $x$ does not divide Bob's current secret value $N$, then Bob subtracts $x$ from $N$ (and thus replaces his old secret value by $N-x$).


• If the secret value ever becomes non-positive, then Bob wins and the game ends.

Question: Can Alice enforce a win? (As usual, we assume that Alice and Bob use optimal strategies.)

Answer

If Alice plays [3, 7, 5, 8, 6, 15, 4, 10, 27, 12, 9, 20, 13, 24, 19, 60, 32, 40, 38, 30, 72, 120]

and Bob's integer is greater than 202

then Alice wins.

Proof: check 203 through 203+120. Check that Alice's strategy covers every residue class (mod 120).

Have fun optimizing 202 down.

I found this sequence using a program and this page. Specifically, Erdos discovered that every integer lies in one of the modular residue classes 0 (mod 3), 0(4), 0(5), 1(6), 1(8), 2(10), 11(12), 1(15), 14(20), 5(24), 8(30), 6(40), 58(60), or 26(120). By inserting numbers between these guesses, Alice can cover all of these residue classes.