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 y multiplicación nimber, que son distintos de la suma ordinal y la multiplicación ordinal.

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 mayor de juegos imparciales. También pueden ocurrir en juegos partisanos como Domineering.

Los Nimbers tienen la característica de que sus opciones Izquierda y Derecha son idénticas, siguiendo un cierto esquema, y que son sus propios negativos, de modo que un ordinal positivo puede agregarse a otro ordinal positivo usando la adición de Nimber para encontrar un ordinal de valor menor.[1] La operación de exclusión mínima se aplica a conjuntos de nimbers.

Usos

Nim

Nim es un juego en el que dos jugadores se turnan para quitar 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 número de objetos siempre que todos provengan del mismo montón. El objetivo del juego es ser el jugador que retire el último objeto. Usando la suma nimber, cada montón se puede sumar para dar un valor nim para el montón. Además, como todos los montones juntos se pueden sumar usando la suma nim, se puede calcular el nimber del juego como un todo. La estrategia ganadora de este juego es forzar el nimber acumulativo del juego a 0 para el turno del oponente.[2]

Cram

Cram es un juego que a menudo se juega en un tablero rectangular en el que los jugadores se turnan para colocar dominós horizontal o verticalmente hasta que no se puedan colocar más dominós. El primer jugador que no pueda hacer un movimiento, pierde. Como los movimientos posibles para ambos jugadores son los mismos, es un juego imparcial y puede tener un valor ágil. Si cada fila y columna se considera un montón, entonces el valor del juego es la suma de todas las filas y columnas usando una suma ágil. Por ejemplo, cualquier tablero 2xn tendrá un nimber de 0 para todos los n pares y un nimber de 1 para todos los n impares.

Juego de Northcott

Un juego donde se colocan clavijas para cada jugador 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, la cantidad de espacios entre las dos fichas en cada fila son los tamaños de los montones de Nim. Si tu oponente aumenta el número de espacios entre dos fichas, simplemente redúcelo en tu próximo movimiento. De lo contrario, juega el juego de Nim y haz que la suma de Nim del número de espacios entre las fichas en cada fila sea 0.[3]

Hackenbush

Hackenbush es un juego inventado por el matemático John Horton Conway. Se puede reproducir en cualquier configuración de segmentos de línea de colores conectados entre sí por sus puntos finales y a una línea de "tierra". los jugadores se turnan para eliminar segmentos de línea. Se puede encontrar una versión de juego imparcial, por lo que se puede encontrar un juego que se pueda analizar usando nimbers eliminando la distinción de las líneas, lo que permite a cualquier jugador cortar cualquier rama. También se eliminan todos los segmentos que dependen del segmento recién eliminado para conectarse a la línea de tierra. De esta manera, cada conexión a tierra puede considerarse un montón de nim con un valor nimber. Además, todas las conexiones separadas a la línea de tierra también se pueden sumar para un poco del estado del juego.

Adición

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

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

donde la exclusión mínima mex(S) de un conjunto S se define de ordinales ser el ordinal más pequeño que es no un elemento de S.

Para los ordinales finitos, la suma nim se evalúa fácilmente en una computadora tomando el bit a bit exclusivo o (XOR, denotado por ⊕) de los números correspondientes. Por ejemplo, la suma nim de 7 y 14 se puede encontrar escribiendo 7 como 111 y 14 como 1110; el lugar de las unidades se suma a 1; el lugar de dos se suma a 2, que reemplazamos con 0; el lugar de cuatro se suma a 2, que reemplazamos con 0; el lugar de los ochos se suma a 1. Entonces, la suma nim 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 de esas estrategias; o puede mostrarse directamente por inducción: Sean α y β dos ordinales finitos, y suponga que la suma nim de todos los pares con uno de ellos reducido ya está definida. El único número cuyo XOR con α ⊕ β es β, y viceversa; por tanto, α ⊕ β se excluye. Por otro lado, para cualquier ordinal γ < α ⊕ β, XORing ξ ≔ α ⊕ β ⊕ γ con todo α, β y γ debe conducir a una reducción para uno de ellos (ya que el 1 inicial en ξ debe estar presente en al menos uno de los tres); dado que ξ ⊕ γ = α ⊕ β > γ, debemos tener α > ξ ⊕ α = β ⊕ γ o β > ξ ⊕ β = α ⊕ γ; por lo tanto γ se incluye como (β ⊕ γ) ⊕ β o como α ⊕ (α ⊕ γ), y por tanto α ⊕ β es el ordinal excluido mínimo.

Multiplicación

La multiplicación de nimber (multiplicación de nim ) se define de forma recursiva por

α β = 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 nimber es el ordinal 0, y la identidad nimber multiplicativa es el ordinal 1. De acuerdo con siendo la característica 2, el nimber aditivo inverso del ordinal α es α mismo. El inverso multiplicativo nimber del ordinal α distinto de cero está 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 de S, entonces [1 + (α′ − α) β′] / α′ es también un elemento de S.

Para todos los números naturales n , el conjunto de nimbers menores que 22n forman el campo de Galois GF(22n) de orden 22n.

En particular, esto implica que el conjunto de nimbers finitos es isomorfo al límite directo cuando n → ∞ de los campos GF(22n). Este subcampo no está algebraicamente cerrado, ya que ningún otro campo GF(2k) (por lo que con k no es una potencia de 2) está contenido en ninguno de esos campos, y por lo tanto no en su límite directo; por ejemplo, el polinomio x3 + x + 1, que tiene una raíz en GF(23), no tiene una raíz en el conjunto de nimbers finitos.

Al igual que en el caso de la adición nímber, existe un medio para calcular el producto nimber de los ordinales finitos. Esto está determinado por las reglas que

  1. El producto nimber de una potencia de Fermat 2 (números de la forma 22n) con un número menor es igual a su producto ordinario;
  2. El cuadrado nimber de un Fermat de 2 potencias x es igual a 3x/2 como se evalúa bajo la multiplicación ordinaria de números naturales.

El campo de nimbers algebraicamente cerrado más pequeño es el conjunto de nimbers menor que el ordinal ωωω, donde ω ies el ordinal infinito más pequeño. De ello se deduce que, como nimber, ωωω es trascendente sobre el campo.[4]

Tablas de sumar y multiplicar

Las siguientes tablas muestran la suma y la multiplicación entre los primeros 16 nimbers.
Este subconjunto está cerrado en ambas operaciones, ya que 16 es de la forma 22n.

Adición de Nimber (sucesión A003987 en OEIS)
Esta es también la tabla de Cayley de Z24 – o la tabla de operaciones XOR bit a bit .Las matrices pequeñas muestran los dígitos únicos de los números binarios.
Multiplicación de números (sucesión A051775 en OEIS)
Los elementos distintos de cero forman la tabla de Cayley de Z15.
Las pequeñas matrices son matrices de Walsh binarias permutadas.
Multiplicación Nimber de potencias de dos (sucesión A223541 en OEIS)
Cálculo de los nim-productos de potencias de dos es un punto decisivo en el algoritmo recursivo de la nimber-multiplication.

Véase también

Notas
  1. Advances in Computer Games (Conference); Herik, H. J. van den; Plaat, Aske; Kosters, Walter (2015). Advances in computer games: 14th International Conference, ACG 2015, Leiden, the Netherlands, July 1-3, 2015, Revised selected papers. ISBN 978-3-319-27992-3. OCLC 933627646. Consultado el 15 de febrero de 2021.
  2. Levitin, Anany (2012). Introduction to the design & analysis of algorithms (en inglés). Pearson. ISBN 978-0-13-231681-1. OCLC 743298766. Consultado el 15 de febrero de 2021.
  3. «Theory of Impartial Games». 3 de febrero de 2009.
  4. Conway 1976, p. 61.

Referencias
  • Conway, John Horton (1976). On Numbers and Games. Academic Press Inc. (London) Ltd.
  • Lenstra, H. W. (1978). Nim multiplication. Report IHES/M/78/211. Institut des hautes études scientifiques. «(hdl=1887/2125) ».
  • Schleicher, Dierk; Stoll, Michael (2004). «An Introduction to Conway's Games and Numbers». .
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.