Double-ended colourful Nim

Created: December 02, 2024 | Updated: December 05, 2024 | Read markdown | About these notes | View in context | Study these flashcards

Some partial results about the Grundy values for double-ended colourful Nim, as discussed at the end of Winning colourful Nim with the eeny-meeny ruleB. At the moment, apart from these basic cases I’ve got no idea in order to how efficiently compute the values for an arbitrary position. The hope would be for a convenient rule like the eeny-meeny rule.

No colour changes

\[\mathcal G(x) \mapsto x\]

One colour change

\[\mathcal G(x, y) \mapsto x \oplus y\]

This is intuitive, you’re effectively playing on two separate Nim piles.

Two colour changes

\[\mathcal G(1, y, 1) = \begin{cases} 1 &\text{if }y =1 \\ 0 &\text{otherwise} \end{cases}\] \[\mathcal G(1, y, 2) = \begin{cases} 2 &\text{if }y=1 \\ 1 &\text{if }y=2 \text{ or }y \ge 4 \\ 3 &\text{if } y = 3 \end{cases}\] \[\mathcal G(1, y, 3) = \begin{cases} 3 &\text{if } y = 1 \\ 2 &\text{if } y = 2 \text{ or } y\ge 4 \\ 1 &\text{if } y = 3 \end{cases}\] \[\mathcal G(1, y, 4) = \begin{cases} 4 &\text{if }y =1,2,3,\text{or }7 \\ 3 &\text{otherwise} \end{cases}\] \[\mathcal G(1, y, 5) = \begin{cases} 5 &\text{if }y=1,2,3, \text{or }5 \\ 4 &\text{if }y=4,6,\text{or }y \ge 8 \\ 3 &\text{if }y = 7 \end{cases}\] \[\mathcal G(1, y, 6) \stackrel?= \begin{cases} 8 &\text{if }y=1,2,3,4,5 \\ 7 &\text{otherwise } \end{cases}\]

(haven’t proven the last one)

Other rules

  • $\mathcal G(x _ 1, \ldots, x _ n) = \mathcal G(x _ n, \ldots, x _ 1)$ (because the game is symmetric)
  • Guess:
    • $\mathcal G(x, y, z) = 0$ iff $x = z$ and $y \ne x, z$
    • If $x = y = z$, then $\mathcal G(x, y, z) = x$.
    • (probably wouldn’t be hard by induction)

Table of values

| (n1, n2, n3) | G(n1, n2, n3) | | ———— | ————- | | $(1,1,1)$ | $1$ | | $(2,1,1)$ | $2$ | | $(3,1,1)$ | $3$ | | $(1,2,1)$ | $0$ | | $(2,2,1)$ | $1$ | | $(3,2,1)$ | $2$ | | $(1,3,1)$ | $0$ | | $(2,3,1)$ | $3$ | | $(3,3,1)$ | $1$ | | $(1,1,2)$ | $2$ | | $(2,1,2)$ | $0$ | | $(3,1,2)$ | $1$ | | $(1,2,2)$ | $1$ | | $(2,2,2)$ | $2$ | | $(3,2,2)$ | $3$ | | $(1,3,2)$ | $3$ | | $(2,3,2)$ | $0$ | | $(3,3,2)$ | $2$ | | $(1,1,3)$ | $3$ | | $(2,1,3)$ | $1$ | | $(3,1,3)$ | $0$ | | $(1,2,3)$ | $2$ | | $(2,2,3)$ | $3$ | | $(3,2,3)$ | $0$ | | $(1,3,3)$ | $1$ | | $(2,3,3)$ | $2$ | | $(3,3,3)$ | $3$ | Here’s a longer list of calculations for bigger positions.



Related posts