A number game for two

Question

Alice and Bob play the following number game. A target N is fixed, N being a positive integer. Alice then writes the number 1 on the blackboard. Bob responds with the number 2. Thereafter, at each of their alternating turns, a player responds by adding to the last number written by the other player any of the nonzero digits of that number. The first player to reach or surpass the target N wins.

I would like to know for which values of N there is a winning strategy for Alice. Is there a quick way of deciding whether for a arbitrary integer there such a strategy for Alice?

Answer 1

Bob has by far the best of this game. I wrote a terribly inefficient python script to determine the winner, with perfect play, for targets from $17$ through $999$. It reports that Alice wins only for the following targets:

23
24
29
30
31
32
36

Here is the script, in case you want to check it:

from functools import reduce

def followers(n):
    digits = [int(c) for c in str(n) if c != '0']
    return {n+d for d in digits}

def pending(N):
    vals = reduce(lambda x,y:x|y, successors.values(), set())
    return [v for v in vals if v < N and v not in successors.keys()]

successors = { }
successors[16] = followers(16)
p = pending(100)

def makeSucessors(limit):
    global successors

    successors = { }
    successors[16] = followers(16)
    p = pending(limit)
    while p:
        for v in p:
            successors[v] = followers(v)
        p = pending(limit)

makeSucessors(1000)

def winner(target):
    goals = set(range(target, target+9))
    winners = set()
    losers = set()
    losers = {k for k in successors if k < target and goals & successors[k]}
    while 16 not in winners | losers:
        winners |= {k for k in successors if 
                         successors[k] .issubset(losers)}
        losers |= {k for k in successors if 
                         successors[k] & winners}
    return 'Alice' if 16 in winners else 'Bob'

for n in range(17,1000):
    if winner(n)=='Alice': print(n)

It's tempting to conjecture that Bob wins for all sufficiently large targets (where "sufficiently large" may mean $> 36$) but I have no idea how to even approach the problem.

Answer 2

I have tested values from 1 to a little over 300 by hand to see which player has access to which number, and I have found two interesting things. Firstly, there seem to be a finite number of unobtainable target values. My list currently stands as {3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 21, 23, 25, 27, 29, 31, 43, 47, 51, 55, 60, 65, 73, 87, 95}.

Secondly, after the 16th turn (Bob's eighth turn), any number that is obtainable in that turn remains obtainable through some route, which means that the only numbers that I needed to observe were those that had not appeared before, as all other numbers had been explored fully. For example, take 20. You could either add 0 or 2, which means you could have either a 22 next round or remain at a constant 20. This means that a 20 is always possible once one has appeared, and in the following round, a 22 is always possible. Because the 20 cannot produce any new values, I did not have to pay attention to it any longer, and could instead focus on the 22, which can only generate a 24. Because a 20 is always possible and, by extension, a 22 is always possible, so is a 24. This holds true for all numbers greater than or equal to 20, excluding those that are unobtainable. This means that eventually, all of these values can be accessed by either player.

I can also use this idea of only paying attention to newly generated numbers to prove that the earlier numbers are unobtainable. Any numbers I ceased paying attention to were those that could always be generated after that round. If they could always be generated, they would have no new effect on the list, and as such I could safely ignore them, since any numbers they can generate would already be in the list permanently. If no new numbers have a value less than an unobtained value, then it must be impossible to obtain, as no previous values were able to generate it up until that point and the only numbers that can be generated are larger than their base.

This is less of an answer and more of me sharing my findings and hoping they can have some use to someone with more mathematical experience/knowledge than I.

Answer 3

This is far from a complete answer (this really isn't much more than saulspatz's answer). I think this game (at least in isolation) is complicated because base $10$ offers many different nonzero digits, so I investigated arbitrary bases. Base $2$ is trivial, with Bob winning the even targets and Alice winning the odd ones. But maybe someone could find a proof of the behavior of base $3$ even if base $10$ is out of reach.

For bases higher than $2$, it appears that one player might win for sufficiently large targets, but it depends non-monotonically on the base.

For bases $3$ through $15$, and targets from $2$ through $1000$, we have: \begin{array}{cccc} \text{base} & \text{usually} & \text{# of exceptions} & \text{max exception}\\ 3 & \text{Alice} & 4 & 11\\ 4 & \text{Alice} & 10 & 21\\ 5 & \text{Alice} & 20 & 43\\ 6 & \text{Alice} & 7 & 12\\ 7 & \text{Bob} & 5 & 13\\ 8 & \text{Alice} & 8 & 14\\ 9 & \text{Alice} & 40 & 104\\ 10 & \text{Bob} & 17 & 36\\ 11 & \text{Alice} & 36 & 102\\ 12 & \text{Bob} & 37 & 64\\ 13 & \text{Bob} & 129 & 38\\ 14 & \text{Bob} & 16 & 206\\ 15 & \text{Bob} & 277 & 509 \end{array} I have the actual lists as well, but I don't know how helpful they'd be.

For the original base $10$ in particular, I tested targets up through $2500$ instead of just $1000$, and it still seems to be the case that Bob wins unless the target is $3$, $4$, between $9$ and $16$ inclusive, or one of $23,24,29,30,31,32,36$ (saulspatz's list).

---

Mathematica code that you can try out at the open Wolfram Cloud:

moves[n_, base_, target_] := 
 moves[n, base, target] = 
  If[n >= target, {}, 
   Map[# + n &, Complement[Union[IntegerDigits[n, base]], {0}]]]
nextwins[n_, b_, t_] := 
 nextwins[n, b, t] = AnyTrue[moves[n, b, t], Not[nextwins[#, b, t]] &]
alicewins[b_, t_] := Not[nextwins[1, b, t]]
alicebase[b_] := 
 Block[{$RecursionLimit = Infinity}, 
  Table[If[alicewins[b, i], i, Nothing], {i, 2, 1000}]]
bobbase[b_] := Complement[Range[2, 1000], alicebase[b]]