23
$\begingroup$

Consider the following game (that I made up). Two players each attempt to name a target number. The first player begins by naming 1. On each subsequent turn, a player can name any larger number that differs from the current number by a divisor of the current number, including itself. For example, if the current number were 6, the next number named could be any one of 7, 8, 9, or 12. A player that names the target number wins. A player forced to name a number larger than the target number loses.

If the target number is odd, the first player can win trivially by always naming an odd number, because the difference between the current number and the target number is even, and no odd number has an even divisor. The thing I can't seem to figure out is whether the first player also has a winning strategy for every even number greater than 6, and what that strategy is if so. Obviously, one can determine the optimum course of play for any target number by working backward, and doing so seems to suggest the first player can always win, but I haven't been able to understand why.

Is there any way to prove that the first player can always win for any number greater than 6?

$\endgroup$
  • 6
    $\begingroup$ Why the close votes? This seems like a fine question to me. $\endgroup$ – Timothy Chow Sep 30 at 17:22
  • 2
    $\begingroup$ I recommend that you try computing the nimbers of all the game states for small numbers to see if there is a pattern. $\endgroup$ – Timothy Chow Sep 30 at 17:27
  • 1
    $\begingroup$ @TimothyChow I have been working on this problem since it is posted. If we let $w(N, M)$ be $0$ or $1$ according to whether, with target number $N$, a player facing number $M$ will win. Then it seems that for any given $M$, the sequence $\{w(N, M)\}_N$ converges to the parity of $M$. Also, for odd $N$ we always have $w(N, M)$ equal to the parity of $M$. However, if we let $n(N, M)$ be the corresponding nimber, then the sequences $\{n(N, M)\}_N$ don't seem to converge, and I don't observe any pattern of $\{n(N, M)\}$ for odd $N$. Thus I find that the nimber approach is perhaps not correct.. $\endgroup$ – WhatsUp Sep 30 at 18:16
  • 2
    $\begingroup$ @BenoîtKloeckner I tried to prove it with the "stealing winning strategy" trick, assuming that $2$ is a losing position and going upwards. But things start to diverse at around $18$ (i.e. one should discuss whether $18$ is winning or losing, both possibilities are not ruled out by previous values), and there doesn't seem to be a contradiction as far as $60$, and my feeling is that it's not a promising method... $\endgroup$ – WhatsUp Sep 30 at 18:19
  • 3
    $\begingroup$ I wonder if the "$d$-approximation" to this game is any easier to analyze, and if so, whether it yields any insight into the original game. Fix a positive integer $d$. Let $x$ denote the current number and let $y$ denote the number I am about to name. By the "$d$-approximation" I mean the variant of the game in which $y-x$ must not only be a divisor of $x$, but must also not exceed $d$. $\endgroup$ – Timothy Chow Sep 30 at 20:32
5
$\begingroup$

Not an answer.

For those who want to see the nimbers of these games, I have written the following code, which calculates the nimbers for the games with target $N$ from $2$ to $999$.

How to use it:

go to this sagecell page and paste the following text there, then press "Evaluate".

def Nim(N):
    a = [0] * (N + 1)
    maxNim = 4
    for i in range(N - 1, 0, -1):
        f = [False] * maxNim
        for d in divisors(i):
            if i + d > N: continue
            f[a[i + d]] = True
        j = 0
        while j < maxNim:
            if f[j] == False: break
            j += 1
        f = []
        a[i] = j
        if j == maxNim: maxNim *= 2
    return a

for n in range(2, 1000):
    print(n, Nim(n)[1:])

Each line of the output looks like this:

(4, [0, 2, 1, 0])

This means: if the target number is $4$, then a player facing number $1, 2, 3, 4$ has nimber $0, 2, 1, 0$, respectively.


It seems that it's not clear whether my comment above about the convergence of $\{n(N, M)\}_N$ is correct.

Up to $N = 999$:

the sequence $\{n(N, 2)\}$ seems to converge after $N = 72$;

the sequence $\{n(N, 4)\}$ seems to converge after $N = 282$;

the sequence $\{n(N, 6)\}$ seems to converge after $N = 160$.

However:

the sequence $\{n(N, 8)\}$ only converges after $N = 910$.

So it's fair to say that it's still not clear whether $\{n(N, 8)\}$ converges.

Similar things happen with $\{n(N, 16)\}$ etc.

$\endgroup$
3
$\begingroup$

I think that every even target greater than $6$ is indeed a first player win. I have no proof but present evidence and speculation on what might lead to a proof.

For every even target at least up to $10000$ there is a strategy which is $2k \rightarrow 2k+1$ except for a small list of exceptions. For example

  • Target $T=9580$

    Strategy: The other player will always state even numbers. Our response should be $2k \rightarrow 2k+1$ with these four exceptions $$4786 \rightarrow 7179,\ 7184 \rightarrow 7633,\ 9100 \rightarrow 9105,9572 \rightarrow 9574,\ 9578\rightarrow 9580$$

Let me justify that. Consider the sets $$W=\{9574,9580\}$$ $$L=\{4787,7185,9101,9573,9575,9579\}$$

These are the even numbers which it is a winner to state and the odd numbers which it is a loser to state. If the opponent never states a member of $W,$ they can't win. But those are $T=2^2\cdot 5\cdot 479$ and $9574=2\cdot 4787 .$ If we never state the odd numbers $9579,9575,9101,7185=T-1,T-5,T-479,T-2395$ or $4787=9574-4787,$ then they can't state anything from $W$ , unless perhaps we state an even number. We could state $9580$ and win. And if we state $9574=2\cdot 4787$ they can only reply $9576$ to which we can reply $9577 \notin L.$ So we just need responses other than $2k \rightarrow 2k+1$ for $2k+1 \in L.$ So preferably $2k \rightarrow 2k+t\lt T$ where $t \gt 1$ is an odd divisor of $k$ and $2k+t \notin L$. And we have done this for four of the five cases.For $9573-1=9572=2^2\cdot 2393$ there is no such $t$ to use. Fortunately, $9572 \rightarrow 9574$ allows us to state a winner.

OPTIONAL DIGRESSION: Here are three more examples

  • target $T=2^j$:

    Strategy: $2k\rightarrow 2k+1$ except $2^k-2 \rightarrow 2^k.$ So $W=\{2^k\}\ \ L=\{2^k-1\}.$

  • target $T=2p$ for $p$ prime but not a Fermat prime $p=2^s+1.$

    Strategy: $2k \rightarrow 2k+1$ except $2p-2 \rightarrow 2p$ and $p-1 \rightarrow p-1+t$ where $t \gt 1$ is the next smallest odd divisor. So $W=\{2p\}\ \ L=\{p,2p-1\}.$

Since $p-1$ is not a power of $2,$ there is such an odd divisor.

  • target $T=2p$ for $p$ a Fermat prime $p=2^s+1:$

    Strategy: $2k \rightarrow 2k+1$ except $2p-2 \rightarrow 2p$ and $p-3 \rightarrow p-3+t$ where $t\gt 1$ is the next smallest odd divisor (so also $t \gt 3.$). here $W=\{p-1,2p\}\ \ L=\{p,2p-3\}.$

Since $p-1=2^s$ it is actually an even winner as the only responses are $p$ and even losers.

END OF DIGRESSION

Question which arise are:

  • How do we come up with the (or a) valid strategy?

  • How can we rule out $1 \in L?$

  • How large might the set of exceptions be?


The methods for an even target $T=2n$ is to start $W=\{2n\}$ and $L=\{\}$ where $W$ will be the even winners and $L$ will be the odd losers.

While there are unexamined members of $W \cup L$, consider the largest such.

  • If it is $2k \in W$, then add $2k-t$ to $L$ where $t$ ranges over the odd divisors of $k$. Then pick the next unexamined member.

  • If it is $2f+1 \in L$ then either find a good response to $2f$ or, if there is none, add $2f$ to $W$: Consider $2f+t$ where $t$ goes through the divisors of $2f$, As soon as you get an even winner in $W$ or and odd number not in $L$, add that to your list of exceptional rules. If none of those happen, add $2f$ to $W.$ Then pick the next unexamined member.

Stop when everything currently in $W \cup L$ has been examined.


The exceptions, given an even target $T \gt 6$, are $W,$ the even numbers it is a winner to state and $L$ the odd numbers it is a loser to state. For $\mathcal{T}$ a set of even targets (such as all even integers greater than $6$), One way to prove that every $T \in \mathcal{T}$ is a first player win is to show that every $T \in \mathcal{T}$ has smallest exception $e \gt 1$.

A stronger result might be easier. I would conjecture that $e \gt \frac{T}{4}.$

For even $6 \lt T \lt 10000$ there are $114$ cases where $\frac{e}{T} \lt \frac{15}{41}.$ Here are the first few pairs $[T,e]$ if we sort according to increasing ratio $\frac{e}{T}$

$$[114,31],[10,3],[30,9],[462,151],[130,43],[450,151],[1254,421],[2058,691],[1250,421],[3654,1231],[2050,691],[2530,853],[3650,1231],[4930,1663],[5730,1933],[8454,2851],[8450,2851],[9250,3121],[9570,3229]$$

So $\frac{e}{T} \gt \frac14$ (up to $T=10000$) and $\frac{e}{T} \gt \frac13$ for $T \gt 130.$ On the other hand, there are $T$ on the edge of the examined range with $\frac{e}{T} \lt 0.337$


There are $12$ cases for $4 \leq T \leq 10000$ with $2$ exceptions, The powers of $2.$

However there are $1285$ with exceptional set of size $3$, all cases of $T=2p$ and some, but not all, $T=2^sp$ for larger $s.$

Here are the first few counts: $$[2, 12], [3, 1285], [4, 28], [5, 609], [6, 187], [7, 60], [8, 525].$$ The largest are $72,75,80,83,84,94,97$ which occur once each.

Here is a cumulative plot

enter image description here

So just under $\frac23$ of the cases have exceptional sets of size $12$ or less and over $90\%$ have exceptional set of size $25$ or less.


You can just say that the target is the largest number which can be stated and the first player without a move loses. I didn't consider the case of first player without a move wins, but it should be largely similar.

$\endgroup$

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.