Nim variant (?) with integer division

Question

I'm trying to analyze different variants of the classic Nim rules, and this set of rules is stumping me a little bit.

• Two players
• One heap, initial size $k$
• Each turn, the player removes one item from the heap and then divides the number of items by either 2, 3 or 7. Here, "divides" is understood as integer division, i.e. discarding the remainder.
• Misère-like; the first player to leave an empty heap to their opponent wins.

I'm trying to solve for $k$ the question: which player (first to play or second to play) has a winning strategy.

I have written a recursive algorithm that is basically brute-force enumeration of all the possible moves in a game:

function OUTCOMES(k)
  if k != 0
    k := k - 1
    for move_first in { 2, 3, 7 }
      k_div := k / move_first
      if k_div = 0 return FIRST_PLAYER
    
      l := k_div - 1
      if all { move_second ∈ { 2, 3, 7 }, OUTCOMES(l / move_second) = FIRST_PLAYER }
        return FIRST_PLAYER
      end
    next
  end if

  return SECOND_PLAYER
end

Obviously, this is not optimal, and I've been trying to find a systematic way to find the player with winning strategy from the number k.

There is a pattern: (k growing left to right, then top to bottom, color = first or second player wins)

But I'm unable to find a "general formula" in the form $k \mapsto\{\mathrm{FIRST}, \mathrm{SECOND}\}$.

• Is that a "valid Nim"? (is it reducible to one-heap Nim)
• Is there a direct solution to my problem?

Answer 1

It is still brute force, but you can be much more efficient about it than that code. Instead of thinking of heap sizes as "first player win/second player win", think of them instead as "current player win/current player loss". You start identifying winning vs losing positions from the bottom, and remember them, so you don't have to keep redoing those calculations. Winning positions come in ranges, and losing positions come in ranges. Because of the rules of play here, those ranges can be identified in mass rather than one at a time (using $\langle a,b\rangle$ to denote the integers from $a$ to $b$):

• $k = 0$: Loss
• $\langle 1, 7\rangle$: Win. Subtract $1$ and divide by $7$ to leave the losing position $0$ to the other player. (In the future, I will not mention the mandatory subtraction of $1$, just the divisions.)
• $\langle 8, 16\rangle$: Loss. Dividing by $2,3,$ or $7$ will leave a result in $\langle 1, 7\rangle$.
• $\langle 17, 34\rangle$: Win. Divide by $2$ to leave a result in $\langle 8, 16\rangle$
• $\langle 35, 51\rangle$: Win. Divide by $3$ to leave a result in $\langle 8, 16\rangle$
• $\langle 52, 56\rangle$: Loss. Dividing by $2$ or $3$ gives a result in $\langle 17, 34\rangle$, Dividing by $7$ gives a result in $\langle 1, 7\rangle$.
• $\langle 57, 119\rangle$: Win. Dividing by $7$ gives a result in $\langle 8, 16\rangle$

If $\langle a,b\rangle$ is a loss range, then $\langle na+1, n(b+1)\rangle$ will be a win range, where $n=2,3,$ or $7$, because the player can convert the heap size to the loss range to pass on to the other player. So for each loss range, you calculate the three win ranges and add them to your list. Anything between win ranges is another loss range.

The next loss range to evaluate above is $\langle 52, 56\rangle$, which produces the three win ranges $\langle 105, 114\rangle, \langle 157, 171\rangle, \langle 365, 399\rangle$. The first falls within an already identified win range, so contributes nothing new. Because $\langle 120, 156\rangle$ is between win ranges, it is the next loss range. But it also contributes win ranges $\langle 241, 314\rangle$ and $\langle 361,471\rangle$, which subsumes the previously identified $\langle 365, 399\rangle$ win range.

Because of these overlaps and the odd interplay of the three multipliers, it would be very unlikely to have a nice formula. But finding winning and losing ranges as above is a lot faster than how you were doing it.