Nimber

En matemáticas, los nimbers, también llamados números de Grundy, se introducen en la teoría de juegos combinatorios, donde se definen como los valores de montones en el juego Nim. Los nimbers son los números ordinales dotados de suma de nimbers y multiplicación de nimbers, que son distintos de la suma de ordinales y la multiplicación de ordinales.

Debido al teorema de Sprague-Grundy que establece que todo juego imparcial es equivalente a un montón de Nim de cierto tamaño, los nimbers surgen en una clase mucho más grande de juegos imparciales. También pueden ocurrir en juegos partidistas como Domineering.

Los nimbers tienen la característica de que sus opciones Left y Right son idénticas, siguiendo un cierto esquema, y que son sus propios negativos, de modo que un ordinal positivo se puede sumar a otro ordinal positivo usando la suma de nimbers para encontrar un ordinal de un bajo valor. La operación mínima excluyente se aplica a conjuntos de números.

Usos

Nim

Nim es un juego en el que dos jugadores se turnan para retirar objetos de distintos montones. Como los movimientos dependen solo de la posición y no de cuál de los dos jugadores se está moviendo actualmente, y donde los pagos son simétricos, Nim es un juego imparcial. En cada turno, un jugador debe eliminar al menos un objeto y puede eliminar cualquier cantidad de objetos, siempre que todos provengan del mismo montón. El objetivo del juego es ser el jugador que retira el último objeto. El número de un montón es simplemente el número de objetos en ese montón. Usando la suma de nim, uno puede calcular el nimber del juego como un todo. La estrategia ganadora es forzar el número del juego a 0 para el turno del oponente.

Embarazarse

Cram es un juego que a menudo se juega en un tablero rectangular en el que los jugadores se turnan para colocar fichas de dominó, ya sea horizontal o verticalmente, hasta que no se puedan colocar más fichas de dominó. El primer jugador que no puede hacer un movimiento pierde. Como los movimientos posibles para ambos jugadores son los mismos, es un juego imparcial y puede tener un valor más ágil. Por ejemplo, cualquier tablero que tenga un tamaño par por un tamaño par tendrá un número de 0. Cualquier tablero que sea par por un tamaño impar tendrá un número distinto de cero. Cualquier tablero 2×n tendrá un número de 0 para todos, incluso n y un número de 1 para todos los n impares.

El juego de Northcott

En el juego de Northcott, las fichas de cada jugador se colocan a lo largo de una columna con un número finito de espacios. Cada turno, cada jugador debe mover la pieza hacia arriba o hacia abajo en la columna, pero no puede pasar la pieza del otro jugador. Varias columnas se apilan juntas para agregar complejidad. El jugador que ya no puede hacer ningún movimiento pierde. A diferencia de muchos otros juegos relacionados con nimber, el número de espacios entre las dos fichas en cada fila es el tamaño de los montones de Nim. Si tu oponente aumenta el número de espacios entre dos fichas, simplemente disminúyelo en tu próximo movimiento. De lo contrario, juegue el juego de Nim y haga que la suma de Nim del número de espacios entre las fichas en cada fila sea 0.

Hackenbush

Hackenbush es un juego inventado por el matemático John Horton Conway. Se puede jugar en cualquier configuración de segmentos de líneas de colores conectados entre sí por sus extremos y a un "suelo" línea. Los jugadores se turnan para eliminar segmentos de línea. Se puede encontrar una versión imparcial del juego, por lo tanto, un juego que pueda analizarse utilizando nimbers, eliminando la distinción de las líneas, lo que permite que cualquier jugador corte cualquier rama. Cualquier segmento que dependa del segmento recién eliminado para conectarse a la línea de tierra también se eliminará. De esta forma, cada conexión a tierra puede considerarse un montón nim con un valor nimber. Además, todas las conexiones separadas a la línea de tierra también se pueden sumar para un número del estado del juego.

Adición

La adición de nimber (también conocida como adición de nim) se puede utilizar para calcular el tamaño de un solo montón de nim equivalente a una colección de montones de nim. Se define recursivamente por

α ⊕ β = mex({α⊕ β: α '. α.α ⊕ β′: β′′ β}),

donde el mínimo excluyente mex(S) de un conjunto S de ordinales se define como el ordinal más pequeño que no es un elemento de S.

Para los ordinales finitos, la suma-nim se evalúa fácilmente en una computadora al tomar el bit a bit exclusivo o (XOR, denotado por ⊕) de los números correspondientes. Por ejemplo, la suma mínima de 7 y 14 se puede encontrar escribiendo 7 como 111 y 14 como 1110; el lugar de las unidades suma 1; el lugar de los dos suma 2, que reemplazamos con 0; el lugar de los cuatros suma 2, que reemplazamos con 0; el lugar de los ochos suma 1. Entonces, la suma mínima se escribe en binario como 1001, o en decimal como 9.

Esta propiedad de la suma se deriva del hecho de que tanto mex como XOR producen una estrategia ganadora para Nim y solo puede haber una estrategia de este tipo; o se puede mostrar directamente por inducción: Sea α y β ser dos ordinales finitos, y suponer que ya está definida la suma nim de todos los pares con uno de ellos reducido. El único número cuyo XOR con α es α ⊕ β es β, y viceversa; por lo tanto, se excluye α ⊕ β. Por otro lado, para cualquier ordinal γ < α ⊕ β, XORing ξ ≔ α ⊕ β ⊕ γ con todos los α, β y γ deben conducir a una reducción para uno de ellos (ya que el 1 principal en ξ debe estar presente en al menos uno de los tres); ya que ξ ⊕ γ = α ⊕ β > γ, debemos tener α > ξ ⊕ α = β ⊕ γ o β > ξ ⊕ β = α ⊕ γ; por lo tanto, γ se incluye como (β ⊕ γ) ⊕ β o como α ⊕ (α ⊕ γ), y por lo tanto α ⊕ β es el mínimo ordinal excluido.

Multiplicación

La multiplicación de nimbers (nim-multiplication) se define recursivamente mediante

α β = mex({α. β ⊕ α β⊕ α ' β′: α′′ α, β′′ β}).

Excepto por el hecho de que los nimbers forman una clase propia y no un conjunto, la clase de nimbers determina un campo algebraicamente cerrado de característica 2. La identidad aditiva del nimber es el ordinal 0, y la identidad multiplicativa del nimber es el ordinal 1. De acuerdo con la característica de ser 2, el inverso aditivo de nimber del ordinal α es α en sí mismo. El nimber multiplicativo inverso del ordinal distinto de cero α viene dado por 1/α = mex(S), donde S es el conjunto más pequeño de ordinales (nimbers) tal que

1. 0 es un elemento de S;
2. si 0 α′′ α y β. es un elemento S, entonces [1 + (α − α) β) / α es también un elemento S.

Para todos los números naturales n, el conjunto de números menores que 2^{2 n} forman el campo de Galois GF(2²ⁿ ) de orden 2²ⁿ. Por lo tanto, el conjunto de nimbers finitos es isomorfo al límite directo como n → ∞ de los campos GF(2 ²ⁿ). Este subcampo no está cerrado algebraicamente, ya que ningún campo GF(2^k) con k ninguna potencia de 2 está contenida en ninguno de esos campos, y por lo tanto no en su límite directo; por ejemplo el polinomio x³ + x + 1, que tiene una raíz en GF(2³), no tiene raíz en el conjunto de nimbers finitos.

Al igual que en el caso de la suma de números, existe una forma de calcular el producto de números de ordinales finitos. Esto está determinado por las reglas que

1. El producto ágil de un Fermat 2 potencia (números de la forma 2²ⁿ) con un número menor es igual a su producto ordinario;
2. El cuadrado de nimber de un Fermat 2-power x es igual a 3x/2 como evaluado bajo la multiplicación ordinaria de números naturales.

El campo algebraicamente cerrado de nimbers más pequeño es el conjunto de nimbers menores que el ordinal ω^ωω, donde ω es el ordinal infinito más pequeño. Se sigue que como un nimber, ω^ωω es trascendental sobre el campo.

Tablas de suma y multiplicación

Las siguientes tablas muestran sumas y multiplicaciones entre los primeros 16 números.
Este subconjunto se cierra en ambas operaciones, ya que 16 tiene la forma 2²ⁿ. (Si prefiere tablas de texto simples, están aquí.)

Nimber addition (sequence A003987 en el OEIS)
Esta es también la mesa de Cayley de Z24 – o la mesa de operaciones bitwise XOR.
Las pequeñas matrices muestran los dígitos únicos de los números binarios.

Multiplicación de madera (sequence) A051775 en el OEIS)
Los elementos no cero forman la mesa de Cayley de Z15.
Las pequeñas matrices son matrices binarias permutadas.

Multiplicación de potencias de dos (secuencia) A223541 en el OEIS)
Calcular los nim-productos de los poderes de dos es un punto decisivo en el algoritmo recursivo de nimber-multiplication.