10
$\begingroup$

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 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.

$\endgroup$
  • $\begingroup$ 1 is on the whiteboard initially. The number on the whiteboard is n. We then choose a divisor - which can only be 1 initially. So Amy has to write 2 on the whiteboard. Then Ben can choose between 1 and 2. Do I get this right? $\endgroup$ – Thomas Weller May 7 at 22:33
  • $\begingroup$ @ThomasWeller, Sorry, but I was sleeping. You are correct. I posted this before I slept. $\endgroup$ – Culver Kwan May 8 at 1:36
6
$\begingroup$

Partial answer: odd $k$ ()

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$.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Even if you land on $k/2$ for $k$ even, you lose. $\endgroup$ – Yuzuriha Inori May 7 at 14:56
4
$\begingroup$

(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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting that for even $k$, the numbers for which that player has a winning strategy are all rot13(gur cerivbhf jvaavat ahzore cyhf n fhpprffviryl vapernfvat cbjre bs gjb). $\endgroup$ – shoover May 7 at 17:11
  • $\begingroup$ @shoover I just realized, while inspecting tables, that I made a terrible error which changes the results! (I computed the divisors of $6$ as $1,2,6$ previously... oops!) I fixed it in the answer. $\endgroup$ – Milo Brandt May 7 at 17:26
  • $\begingroup$ To put code or other preformatted text in a spoiler block, use the <pre>...</pre> tags. You still need >! on each line. $\endgroup$ – Daniel Mathias May 7 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.