Este es Welter del Juego, con especial posiciones de partida. En el capítulo 13 de los Números y los Juegos, John Horton Conway presenta una asombrosa análisis basado en la animación de las funciones." Lo que parece ser su propia temprano de la solución presentada por Welter (pero sin atribución).
Aunque no hay espacio suficiente para dar cuenta completa de este juego, voy a esbozar la teoría, indican cómo los cálculos pueden llevarse a cabo, proporcionar un original algoritmo para calcular los valores de este juego de posiciones de partida y la visualización de los ganadores se mueve. Referencias (al final) se rellene los detalles. Algunos de los códigos que se adjunta para aquellos a los que les gustaría explorar más a fondo.
Por qué esto es Welter del Juego
Vamos a no ser gafas con $k_1, k_2, \ldots, k_n$ bolas. Representan esta configuración, puesta $n$ monedas en una franja horizontal de plazas, numeradas $0, 1, \ldots$ de izquierda a derecha, con una moneda colocada en la plaza de $k_i$ que representan el contenido de vidrio $i$. Las reglas de las gafas juego, traducido a este valor, se
Que Welter del Juego. Por ejemplo, los anteojos con $1,3,6,10$ bolas corresponden a la moneda de configuración:
![Figure]()
Su Grundy valor es $10$ (ver abajo), mostrando que es un triunfo para el siguiente jugador se mueva. La única jugada ganadora es $1,3,4,6$, alcanzado por la eliminación de $6$ bolas de cristal con $10$.
El álgebra de los Welter del Juego
Como en todos los Nim-como juegos, este es completamente determinado por su Grundy valor (también conocido como "Nim", o "nimber"), que es un elemento del conjunto a $\{0,1,2,\ldots\}$. El complemento natural de Grundy valores (Nim, además, escrito ${+}_2$) refleja la adición (o "disyuntiva compuesto") de juegos. Si desactiva la capacidad de su equipo binario para llevar dígitos, se llevará a cabo Nim adición.
El Grundy valor de la posición con $k_1, \ldots, k_n$ bolas está escrito $[k_1|k_2|\cdots|k_n]$. Según Conway, Welter encontrado por la explotación de dos relaciones:
$[0|a|b|c|\cdots] = [a-1|b-1|c-1|\cdots]$. Esto es obvio, porque la moneda en $0$ simplemente acorta la tira entera por uno de los cuadrados.
$[a{+}_2 x|b{+}_2 x|c{+}_2 x|\cdots] = [a|b|c|\cdots]$ cuando el número de argumentos de la $(a,b,c,\ldots)$ es, incluso, y de lo contrario,$[a{+}_2 x|b{+}_2 x|c{+}_2 x|\cdots] = [a|b|c|\cdots]{+}_2 x$.
Mediante la explotación de la segunda relación repetidamente puede simplificar el juego de Nim-la adición de $a$ para producir una $0$ y el uso de la primera relación de reducir el número de argumentos. Esto finaliza rápidamente y en el proceso de escupir desde el Nim-suma de un montón de $x$'s (en cada paso), que genera el Grundy valor de la posición.
Conway se desarrolla un álgebra de "animación de funciones", que comparten muchas de las propiedades de los Complejos de funciones racionales. Con él se demuestra que la Grundy valor de un Cúmulo de posición es una animación de la función, proporcionando la base para muchos la simplificación algebraica de las identidades. Para más detalles, ver Conway; para una breve introducción, se refieren a la persona (referencias al final).
El Grundy los valores de las posiciones de partida
Los valores de partida que surjan en el juego con las gafas son de la forma
$$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)$.
De lo contrario, $w(n) = 3(2^p) + w(n_0)$.
$w(0) = 0$.
Estos pueden ser probadas de forma recursiva el uso de Conway de la animación de la función de álgebra. Los valores de $w(n)$ inicio, comienzo a $n=1$, como
$$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$.
Referencias
John Conway presenta el álgebra de la animación de funciones Sobre Números y Juegos (2ª Ed., A K Peters, Ltd, 2001).
Richard Guy proporciona algoritmos en una monografía Imparcial Juegos (Combinatoria Juegos MSRI Publicaciones Volumen 29, 1995).
Tipo referencias Welter del papel:
C. P. Welter, La teoría de una clase de juegos en una secuencia de plazas,
en términos de la operación de avance en un grupo especial, Nederl. Akad. Wetensch.
Proc. A57 = Indag. De matemáticas. 16 (1954), 194-200.
