Add a divisor! A game

Question

Let $k$ be a positive integer. Amy and Ben are playing a game, with the number $1$ written on the whiteboard initially. Amy and Ben do the following in order, starting with Amy:

Suppose the number on the whiteboard is $n$. The person who is making the turn chooses $d$ which is a divisor of $n$ and replaces the number on the whiteboard with $n+d$.

The player who writes a number larger than $k$ loses. Who has a winning strategy for each $k$?

The winner can be easily determined for odd $k$, so no-computers applies for odd $k$. But for other values, you can write a program and test it out.

---

Edit: Could anyone find the person who has the winning strategy of even $k$ by mathematical proofs? The one who does it will be awarded a checkmark.

Answer 1

Partial answer: odd $k$ (no-computers)

Ben

has a winning strategy, namely

always choose $d=1$ and leave an odd number on the board.

This wins because

Amy is always faced with an odd number and is forced to choose an odd divisor, thereby turning it into an even number. Ben just turns $2r$ into $2r+1$ every time, which means the first person to exceed the odd number $k$ must be Amy.

If computers are required for even $k$, I'll leave that for someone else. I'm no good at programming.

General notes:

• If you write $k$ on the board, you win. If you write $k-1$ or (for $k$ even) $k-2$ on the board, you lose.

• If $k=2$, Amy wins by writing $2$.
  If $k=4$, Ben wins because Amy writes $2$.
  If $k=6$, Amy wins because Ben must write $3$ or $4$.
  If $k=8$, Ben wins by writing $3$ because Amy must write $4$ or $6$.
  If $k=10$, then writing $5$ or $6$ or $8$ or $9$ is a loss, so Ben wins by writing $4$.
  If $k=12$, then writing $6$ or $8$ or $9$ or $10$ is a loss, so Ben wins by writing $3$.

Answer 2

(Not an answer but too long for a comment - computer based)

I checked all the possible games for $1 \leq k \leq 10000$ by computer. I discovered the following:

Amy only has a winning strategy for $k=2,\,6$.

I have no idea why this is, but in case it is of some use, the following spoiler contains a table of the winning and losing positions for even $k$ between $2$ and $20$. Note that "Winning" means "If you start in this position, you have a winning strategy."

Winning positions for k = 2:
1: Winning
2: Losing
Winning positions for k = 4:
1: Losing
2: Winning
3: Winning
4: Losing
Winning positions for k = 6:
1: Winning
2: Losing
3: Winning
4: Winning
5: Winning
6: Losing
Winning positions for k = 8:
1: Losing
2: Winning
3: Losing
4: Winning
5: Losing
6: Winning
7: Winning
8: Losing
Winning positions for k = 10:
1: Losing
2: Winning
3: Winning
4: Losing
5: Winning
6: Winning
7: Losing
8: Winning
9: Winning
10: Losing
Winning positions for k = 12:
1: Losing
2: Winning
3: Losing
4: Winning
5: Losing
6: Winning
7: Losing
8: Winning
9: Winning
10: Winning
11: Winning
12: Losing
Winning positions for k = 14:
1: Losing
2: Winning
3: Losing
4: Winning
5: Losing
6: Winning
7: Winning
8: Winning
9: Losing
10: Winning
11: Losing
12: Winning
13: Winning
14: Losing
Winning positions for k = 16:
1: Losing
2: Winning
3: Losing
4: Winning
5: Losing
6: Winning
7: Losing
8: Winning
9: Losing
10: Winning
11: Losing
12: Winning
13: Losing
14: Winning
15: Winning
16: Losing
Winning positions for k = 18:
1: Losing
2: Winning
3: Losing
4: Winning
5: Losing
6: Winning
7: Winning
8: Losing
9: Winning
10: Winning
11: Losing
12: Winning
13: Winning
14: Losing
15: Winning
16: Winning
17: Winning
18: Losing
Winning positions for k = 20:
1: Losing
2: Winning
3: Losing
4: Winning
5: Losing
6: Winning
7: Winning
8: Winning
9: Losing
10: Winning
11: Losing
12: Winning
13: Winning
14: Losing
15: Winning
16: Winning
17: Losing
18: Winning
19: Winning
20: Losing

Here's the code I used (in C++). It doesn't seem to want to go into a spoiler, but, of course, it's not going to tell you anything interesting unless you run it. It takes a few minutes on my computer to check up to 100000. (If you're not in the habit of running C++, you can use online compilers like this. You probably can't do long computations this way, but you can have it output tables and such for smaller cases)

#include <vector>
#include <iostream>
#include <assert.h>

std::vector<int> const& divisorsOf(int x){ //Memoized function returning divisors calculated by trial division.
    static std::vector<std::vector<int> > cache;
    if(cache.size() >= x){
        return cache[x-1];
    }
    if(x != cache.size() + 1) divisorsOf(x-1); //Compute all divisors before this.
    std::vector<int> divisorList;
    for(int i = 1; i <= x; ++i){
        if(x % i == 0) divisorList.push_back(i);
    }
    cache.push_back(std::move(divisorList));
    return cache.back();
}
void checkCase(int k){
    std::vector<bool> winPositions;
    winPositions.resize(k); //winPositions[k] will be true at the end position k+1 is winning.
    for(int p = k; p > 0; --p){ //Compute positions from the end
        bool winning = false; //A position is winning if it can move to a losing position.
        for(int divisor : divisorsOf(p)){
            if(p + divisor <= k && !winPositions[p + divisor - 1])
                winning = true;
        };
        winPositions[p - 1] = winning;
    }
    //The following lines would print the full table of winning/losing positions:
    /*std::cout << "Winning positions for k = " << k << ":\n";
     for(int p = 1; p <= k; ++p){
     std::cout <<"\t" << p << ": " << (winPositions[p-1]?"Winning":"Losing") << "\n";
     }*/
    //This outputs only whether the first player wins.
    if(winPositions[0])
        std::cout << "First player wins for k = " << k << "\n";
}
int main(int argc, const char * argv[]) {
    int max = 100000;
    for(int i = 1; i <= max; ++i){
        checkCase(i);
    }
    std::cout << "Done. Checked up to " << max << "\n";
    return 0;
}

---

Edit: some non-computer work. It seems like, if you forget about $k$ (assume it's larger than we touch in our logic), you can derive some interesting results from assuming "$1$ is a winning position" then just using that a position is winning if and only if it can move to a losing position. Details spoilered:

In particular you can figure out that $2$ must be a loss, then $3, 4$ must be a win, which, since $3$ can only move to $4$ or $6$ implies that $6$ must be a loss. You can prove, of the positions $1 \leq p \leq 16$, only $p=2,\,6,\,10,\,14$ are losses and the rest are wins from this assumption (and the assumption that $k>16$). There's a smattering of further results for higher positions - most notably, it turns out that $p=22$ is a loss - but nothing as dramatic as a uniquely determined answer.

You would hope to derive a contradiction here, but I realized that this is not possible, because setting any position $p$ equal to $2$ mod $4$ as a loss and the rest as wins satisfies the axiom that a position is a win if and only if it has a move to a loss, since you can add $2$ to anything of the form $4n$ or $1$ to anything of the form $4n+1$, you cannot add a multiple of $4$ to a loss of the form $4n+2$, and then every number of the form $4n+3$ has a prime divisor of the form $4m+3$, so can reach something of the form $4k+2$. So I guess this method doesn't lead to a solution, but it seemed interesting enough to share.