Game to maintain distinct number of balls in glasses

Question

There are $n$ glasses, containing $n+1,n+2,\ldots,2n$ balls, respectively. Two players $A$ and $B$ play a game, alternately taking turns with $A$ going first. In each move, the player must choose some balls (perhaps all, but not empty) from one glass, so that the number of balls remain pairwise distinct. The player who cannot move loses. Who can win?

The position where the game ends must be $0,1,\ldots,n-1$, since otherwise there is a move left. To reach this position, the game must be in the position where $n-1$ of the $n$ glasses coincide with the end position. For $n=1$, $A$ wins after the first move. For $n=2$, $A$ takes off two balls from $4$ to get to $3,2$. Then whatever $B$ does, some glass contains $0$ or $1$ balls, so $A$ wins in the next turn.

Answer 1

If n is even, A's first move is to move n balls out of the 2n-glass. Partner adjacent numbers together in such a manner (0,1), (2,3), (4,5), ..., (2n-2,2n-1). Whenever B turns an n-glass into an m-glass, A responds by turning partner(n)-glass into the partner(m)-glass.

If n is odd, A's first move is to take all balls out of the (n+1)-glass. Then we partner numbers (1,2), (3,4), ..., (2n-1,2n) and do the same as before.

_

---

To see why this works let's work thru an example where $n=6$. The initial setup is

$\;\;\;\;\;\;\;\; \_\__0 \;\;\; \_\__1 \;\;\; \_\__2 \;\;\; \_\__{3} \;\;\; \_\__{4} \;\;\; \_\__{5} \;\;\; \_\__{6} \;\;\; \text{O}_{7} \;\;\; \text{O}_{8} \;\;\; \text{O}_{9} \;\;\; \text{O}_{10} \;\;\; \text{O}_{11} \;\;\; \text{O}_{12} $

where O$_m$ represents a glass with $m$ balls. The game ends when the slots $\_\__k$ are filled for $k=0..5$. Player $A$ makes his first move by taking out $6$ balls from O$_{12}$, resulting in

$\;\;\;\;\;\;\;\; \_\__0 \;\;\; \_\__1 \;\;\; \_\__2 \;\;\; \_\__{3} \;\;\; \_\__{4} \;\;\; \_\__{5} \;\;\; \text{O}_{6} \;\;\; \text{O}_{7} \;\;\; \text{O}_{8} \;\;\; \text{O}_{9} \;\;\; \text{O}_{10} \;\;\; \text{O}_{11} $

The key observation is that there are an even number of slots and an even number of glasses -- so we can pair them.

$\;\;\;\;\;\;\;\; (\_\__0 \;\;\; \_\__1) \;\;\; (\_\__2 \;\;\; \_\__{3}) \;\;\; (\_\__{4} \;\;\; \_\__{5}) \;\;\; (\text{O}_{6} \;\;\; \text{O}_{7}) \;\;\; (\text{O}_{8} \;\;\; \text{O}_{9}) \;\;\; (\text{O}_{10} \;\;\; \text{O}_{11}) $

Now $A$ wants to keep the pairs together. Say player $B$ takes 7 balls out of $\text{O}_9$, forming

$\;\;\;\;\;\;\;\; (\_\__0 \;\;\; \_\__1) \;\;\; (\text{O}_2 \;\;\; \_\__{3}) \;\;\; (\_\__{4} \;\;\; \_\__{5}) \;\;\; (\text{O}_{6} \;\;\; \text{O}_{7}) \;\;\; (\text{O}_{8} \;\;\;\_\__9) \;\;\; (\text{O}_{10} \;\;\; \text{O}_{11}) $

Player $A$ responds by changing $\text{O}_8$ into $\text{O}_3$ (by taking out 5 balls).

$\;\;\;\;\;\;\;\; (\_\__0 \;\;\; \_\__1) \;\;\; (\text{O}_2 \;\;\; \text{O}_{3}) \;\;\; (\_\__{4} \;\;\; \_\__{5}) \;\;\; (\text{O}_{6} \;\;\; \text{O}_{7}) \;\;\; (\_\__8 \;\;\;\_\__9) \;\;\; (\text{O}_{10} \;\;\; \text{O}_{11}) $

This ensures that $A$ always has a valid move after $B$, so player $A$ makes the last move and thus wins.

Answer 2

This is Welter's Game with special starting positions. In chapter 13 of On Numbers and Games, John Horton Conway presents an amazing analysis based on "animating functions." It appears to be his own take on an earlier solution presented by Welter (but without attribution).

Although there is not enough space to give a full account of this game, I will sketch the theory, indicate how the calculations can be carried out, provide an original algorithm to compute the values of this game's starting positions, and display the winning moves. References (at the end) will fill in the details. Some working code is appended for those who might like to explore further.

Why this is Welter's Game

Let there be glasses with $k_1, k_2, \ldots, k_n$ balls. Represent this configuration by putting $n$ coins on a horizontal strip of squares, numbered $0, 1, \ldots$ from left to right, with a coin placed on square $k_i$ representing the contents of glass $i$. The rules of the glasses game, translated to this setting, are

• Coins may not occupy the same square and

• A coin may move to the left into any unoccupied square.

That's Welter's Game. For example, glasses with $1,3,6,10$ balls correspond to this coin configuration:

Its Grundy value is $10$ (see below), showing it is a win for the next player to move. The unique winning move is to $1,3,4,6$, attained by removing $6$ balls from the glass with $10$.

The algebra of Welter's Game

As in all Nim-like games, this one is fully determined by its Grundy value (aka "Nim value" or "nimber"), which is an element of the set $\{0,1,2,\ldots\}$. The natural addition of Grundy values (Nim addition, written ${+}_2$) reflects the addition (or "disjunctive compound") of games. If you turn off the ability of your binary computer to carry digits, it will perform Nim addition.

The Grundy value of the position with $k_1, \ldots, k_n$ balls is written $[k_1|k_2|\cdots|k_n]$. According to Conway, Welter found it by exploiting two relations:

1. $[0|a|b|c|\cdots] = [a-1|b-1|c-1|\cdots]$. This is obvious, because the coin at $0$ simply shortens the entire strip by one square.

2. $[a{+}_2 x|b{+}_2 x|c{+}_2 x|\cdots] = [a|b|c|\cdots]$ when the number of arguments $(a,b,c,\ldots)$ is even and otherwise $[a{+}_2 x|b{+}_2 x|c{+}_2 x|\cdots] = [a|b|c|\cdots]{+}_2 x$.

By exploiting the second relation repeatedly you can simplify the game by Nim-adding $a$ to produce a $0$ and using the first relation to reduce the number of arguments. This quickly terminates and in the process will spit off the Nim-sum of a bunch of $x$'s (at every other step), which yields the Grundy value of the position.

Conway develops an algebra of "animating functions," which share many properties of Complex rational functions. With it he shows that the Grundy value of a Welter position is an animating function, providing the basis for many simplifying algebraic identities. For details see Conway; for a brief introduction, refer to Guy (references at the end).

The Grundy values of the starting positions

The starting values arising in the game with glasses are of the form

$$w(n) = [n+1|n+2|\cdots|2n].$$

As a function of $n$, they limit to a beautiful fractal:

The points are colored according to the lengths of their binary representations. Each time the length is increased, patterns from the previous two lengths are copied to the right and up.

This recursive pattern can be described in terms of the binary representation of $n$, which always begins with a $1$. Suppose there are $p$ remaining digits. If they begin with $0$, let the value they represent be $n_0$. Otherwise, strip that initial $1$ and let the value the remaining $p-1$ digits represent be $n_1$.

• If the next digit is also a $1$, then $w(n) = 2^p + w(n_1)$.

• Otherwise, $w(n) = 3(2^p) + w(n_0)$.

• $w(0) = 0$.

These can be proven recursively using Conway's animating function algebra. The values of $w(n)$ start out, beginning at $n=1$, as

$$2;\ 6, 4;\ 12, 14, 10, 8;\ 24, 26, 30, 28, 20, 22, 18, 16;\ 48, 50, 54, 52, 60, 62, 58, \ldots$$

For example $w(11)$ is computed from $10=1011_2$ as $3(2^3) + w(11_2) = 24 + (2^2 + w(0)) = 28$.

It is immediate that the Grundy values of all starting positions are nonzero. This means the game is a win for the first player, whose best moves are to positions with zero values.

The Grundy values of some special positions

There is not always a unique winning move. For example, the winning moves for $n=3$ from the position $\{4,5,6\}$ (with Grundy value $4$) are to $\{0,5,6\}$, $\{1,4,6\}$, and $\{2,4,5\}$. Conway provides an algorithm to invert the Welter function, allowing one to find winning moves from arbitrary positions.

In the coins-in-glasses game one can prove (again inductively) that for even $n$, $[n|n+1|\cdots|2n-1]=0$, showing that a winning move is to reduce the glass of $2n$ coins to $n$ coins. (For odd $n$, the Grundy values of these positions are always $1$.) For odd $n$, $[n+2|n+3|\cdots|2n]=0$, showing that a winning move is to empty the glass of $n+1$ coins. (Interestingly, the pattern of Grundy values of these positions for even $n$ form the sequence $3,7,3,15,3,7,3,31,3,\ldots$. This is Conway's "mating function" $(n|0)$, which removes all but the terminal $d$ zeros from the binary representation of $n$ and replaces them by $d+1$ ones. For instance with $n=28 = 11110_2$, the $d=1$ terminal zeros are replaced by $d+1=2$ ones, yielding $11_2 = 3$.)

Computation

For those who might wish to explore further, here is some Mathematica code implementing the basic operations (Nim-addition and Conway's mating function) and computing the value of any position in Welter's game (using Conway's algorithm as a Nim-sum of "mated pairs").

sum[a_Integer, b_Integer] /; a >= 0 && b >= 0 := 
  Module[{x = IntegerDigits[#, 2] & /@ {Min[a, b], Max[a, b]}}, 
   n = Length /@ x;
   FromDigits[
    x[[2, 1 ;;  n[[2]] - n[[1]] ]]~Join~
     Mod[x[[1]] + x[[2, n[[2]] - n[[1]] + 1 ;;]], 2], 2]
   ];
sum[0, -1] = sum[-1, 0] = -1;
mate[a_, b_] := sum[a, b] - 1;

welter[x_List] := welter[x] =  Module[{d, w},
   w[y_, e_] /; Length[y] >=  2 := Module[{f, i, u, v},
     i = First@Position[e, Max[e], {2}, 1];
     u = mate @@ Part[y, i];
     v = Drop[Drop[y, {Max[i]}], {Min[i]}];
     f = Drop[Drop[e, {Max[i]}, {Max[i]}], {Min[i]}, {Min[i]}];
     sum[u, w[v, f]]
     ];
   w[y_, e_] /; Length[y] == 1 := First@y;
   w[{}, e_] := 0;
    d = Outer[IntegerExponent[Abs[#1 - #2], 2] &, x, x] /. Infinity -> -1;
   w[x, d]
   ]

For example, With[{n=7}, welter[Range[n+1,2 n]]] returns the value 8, which is the Grundy value of the coins-in-glasses game for $n=7$.

References

John Conway presents the algebra of animating functions in On Numbers and Games (2nd Ed., A K Peters, Ltd, 2001).

Richard Guy provides algorithms in a monograph Impartial Games (Combinatorial Games MSRI Publications Volume 29, 1995).

Guy references Welter's paper:

C. P. Welter, The theory of a class of games on a sequence of squares, in terms of the advancing operation in a special group, Nederl. Akad. Wetensch. Proc. A57 = Indag. Math. 16 (1954), 194-200.