14
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ The question states that a player can remove all the balls, but then the end state you give does not include $0$. Must every glass remain nonempty? $\endgroup$ – Peter Woolfitt Dec 20 '14 at 17:37
  • 1
    $\begingroup$ @Meelo But if $B=A+1\geq 2$, then the next player can take two stones from $B$, resulting in $A,A-1$. $\endgroup$ – Alexi Dec 21 '14 at 5:28
  • 1
    $\begingroup$ Oh dang, I didn't think of that. Good thing I'm not playing a game of this against you. Working it out again, it's clear that the correct statement for 2 glasses is that, representing the game's state as a pair $(A,B)$, we have $(2n,2n+1)$ is a losing position; the winning strategy is to, given the state $(2n+1,B)$ or $(2n,B)$ with $B>2n+1$, you should move to $(2n,2n+1)$. (It's easy to verify the correctness of this; shame that I, nonetheless, got it wrong in my last comment) $\endgroup$ – Milo Brandt Dec 21 '14 at 5:36
  • 1
    $\begingroup$ It might be worth considering that when you reduce a bin to $0$, you can think of it as knocking out that bin and reducing all the other bins by $1$. $\endgroup$ – Thomas Andrews Dec 23 '14 at 4:50
  • 2
    $\begingroup$ In particular, if $A$ loses for $n$, $A$ wins for $n+1$ by reducing $2n+2$ to $0$, which is equivalent to knocking out that bin and reducing all the other bin by $1$, getting the starting position for $n$ with $B$'s turn. So, at minimum, the $\liminf$ of the density of the $n$ for which $A$ wins is at least $1/2$. :) $\endgroup$ – Thomas Andrews Dec 23 '14 at 4:58
8
$\begingroup$

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.

$\endgroup$
0
8
+50
$\begingroup$

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:

Figure

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:

Figure

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.

$\endgroup$
1
  • 3
    $\begingroup$ Excellent exposition! By the way, Nim-addition is ubiquitous these days. Programmers call it exclusive-or (or simply XOR), and write it (usually) as a ^ b; cryptographers call it addition in $GF(2)$, and write it as a $\oplus$ b. (Also Mathematica has BitXor[a,b], which is a bit more succinct than your sum function.) $\endgroup$ – TonyK Jan 10 '15 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.