A Combinatorial Game with Integer Sequences

Question

Two players, Alice and Bob, take turns constructing a sequence $a_1,a_2,a_3,\dots$, of distinct positive integers, none greater than a given parameter $K$. Alice plays first and makes $a_1=1$. Thereafter, on the $n$-th move, the player whose turn it is plays $a_n=a_{n-1}+n,a_{n-1}\times n,a_{n-1}\div n$, or $a_{n-1}-n$, whichever he or she chooses provided $a_n$ is a positive integer not already in the sequence, and $\le K$.

The player who makes the last legal move wins.

For which values of $K$ does Alice have a winning strategy?

Answer 1

Not an answer, but some quick data that may help.

On Alice's first move, she only has one option, so her Grundy value is either 0 (no winning strategy) or 1 (a winning strategy). More interesting is the first Grundy value that Bob sees. Some quick Mathematica coding gets the Grundy values for $K\leq 100$.

Mex[A_] := Module[{m = 0}, While[MemberQ[A, m], m++]; m];
opts[K_, chosen_] := 
  Module[{move = Length[chosen] + 1, last = Last[chosen]},
   next = 
    Select[{last + move, last - move, last*move, last/move}, 
     IntegerQ[#] && 1 < # <= K && Not[MemberQ[chosen, #]] &];
   Map[Append[chosen, #] &, next]];
gv[K_, {}] = 0;
gv[K_, chosen_] := Mex[gv[K, #] & /@ opts[K, chosen]];
ParallelTable[gv[K, {1}]], {K, 1, 100}]

The Grundy values that Bob sees are 0, 1, 1, 1, 2, 2, 0, 0, 0, 0, 0, 0, 1, 1, 2, 1, 1, 0, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 0, 0, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 2, 1, 0, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 0, 0, 0, 0, 0, 2, 0, 0, 0,.... In other words, Bob cannot win (unless Alice allows it) for $K \in \{1,7,8,9,10,11, 12, 18, 41, 42, 50, 51, 52, 53, 55, 56, 57, 58, 59, 62, 73, 75, 76, 77, 92, 93, 94, 95, 96, 98, 99, 100,\dots\}$. Is there ever a Grundy value of 3 or 4? No, as Bob only has two options $a_2=2$, $a_2=3$ for the second move of the game. But deep inside the game, perhaps 3's and 4's happen.

Neither the sequence of Grundy values nor the good-for-Alice $K$ are in the OEIS.