Nimber

Número utilizado en la teoría de juegos combinatorios

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

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

Las operaciones de adición y multiplicación de números son asociativas y conmutativas. Cada número es su propio inverso aditivo . En particular, para algunos pares de ordinales, la suma de sus números es menor que la de cada sumando. ^[1] La operación de exclusión mínima 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 únicamente de la posición y no de cuál de los dos jugadores se está moviendo en ese momento, y donde los pagos son simétricos, Nim es un juego imparcial. En cada turno, un jugador debe retirar al menos un objeto, y puede retirar cualquier cantidad de objetos siempre que todos provengan del mismo montón. El objetivo del juego es ser el jugador que retire el último objeto. El nimber de un montón es simplemente la cantidad 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 nimber del juego a 0 para el turno del oponente. ^[2]

Atestar

Cram es un juego que se juega a menudo 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. 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 de nimber. Por ejemplo, cualquier tablero que sea de tamaño par por un tamaño par tendrá un nimber de 0. Cualquier tablero que sea par por impar tendrá un nimber distinto de cero. Cualquier tablero de 2 × n tendrá un nimber de 0 para todos los n pares y un nimber 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. En 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. Se apilan varias columnas juntas para agregar complejidad. El jugador que ya no puede hacer ningún movimiento pierde. A diferencia de muchos otros juegos relacionados con el Nimber, la cantidad de espacios entre las dos fichas en cada fila es el tamaño de los montones de Nim. Si tu oponente aumenta la cantidad de espacios entre dos fichas, simplemente disminúyela en tu siguiente movimiento. De lo contrario, juega el juego de Nim y haz que la suma de Nim de la cantidad 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 jugar 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 imparcial del juego, es decir, un juego que se pueda analizar utilizando nimbers, eliminando la distinción de las líneas, lo que permite a cada 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 se puede considerar un montón de nim con un valor de nimber. Además, todas las conexiones independientes a la línea de tierra también se pueden sumar para obtener un nimber del estado del juego.

Suma

La suma de nim (también conocida como nim-addition ) 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 recursivamente por donde el mex( S ) excluyente mínimo de un conjunto S de ordinales se define como el ordinal más pequeño que no es un elemento de S . $${\displaystyle \alpha \oplus \beta =\operatorname {mex} \!{\bigl (}\{\alpha '\oplus \beta :\alpha '<\alpha \}\cup \{\alpha \oplus \beta ':\beta '<\beta \}{\bigr )},}$$

Para los ordinales finitos, la suma nim se evalúa fácilmente en una computadora tomando la operación exclusiva o (XOR, denotada 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; la posición de las unidades suma 1; la posición de los dos suma 2, que reemplazamos por 0; la posición de los cuatros suma 2, que reemplazamos por 0; la posición de los ochos suma 1. Entonces, la suma nim se escribe en binario como 1001, o en decimal como 9.

Esta propiedad de la adición se sigue del hecho de que tanto mex como XOR producen una estrategia ganadora para Nim y sólo puede haber una estrategia de este tipo; o puede demostrarse directamente por inducción: Sean α y β dos ordinales finitos, y supongamos que la suma nim de todos los pares con uno de ellos reducido ya está definida. El único número cuyo XOR con α es α ⊕ β es β , y viceversa; por tanto, α ⊕ β queda excluido. Por otro lado, para cualquier ordinal γ < α ⊕ β , la XOR de ξ con todos los α , β y γ debe 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 cualquiera de los dos , por tanto, γ se incluye como cualquiera de los dos y, por tanto, α ⊕ β es el ordinal mínimo excluido. $${\displaystyle \zeta :=\alpha \oplus \beta \oplus \gamma }$$ $${\displaystyle \zeta \oplus \gamma =\alpha \oplus \beta >\gamma ,}$$ $${\displaystyle {\begin{aligned}\alpha >\zeta \oplus \alpha &=\beta \oplus \gamma ,\\[4pt]\beta >\zeta \oplus \beta &=\alpha \oplus \gamma ;\end{aligned}}}$$ $${\displaystyle {\begin{aligned}(\beta \oplus \gamma )\oplus \beta ,\\[4pt]\alpha \oplus (\alpha \oplus \gamma );\end{aligned}}}$$

La adición de nimbers es asociativa y conmutativa , con 0 como elemento identidad aditivo . Además, un nimber es su propio inverso aditivo . ^[4] De ello se deduce que α ⊕ β = 0 si y solo si α = β .

Multiplicación

La multiplicación de Nimber ( nim-multiplication ) se define recursivamente por

$${\displaystyle \alpha \,\beta =\operatorname {mex} \!{\bigl (}\{\alpha '\beta \oplus \alpha \,\beta '\oplus \alpha '\beta ':\alpha '<\alpha ,\beta '<\beta \}{\bigr )}.}$$

La multiplicación de números es asociativa y conmutativa, y el ordinal 1 es el elemento de identidad multiplicativo . Además, la multiplicación de números se distribuye sobre la suma de números. ^[4]

Así, salvo que los nimbers forman una clase propia y no un conjunto, la clase de nimbers forma un anillo . De hecho, incluso determina un cuerpo algebraicamente cerrado de característica 2, con el inverso multiplicativo de nimber de un ordinal α distinto de cero dado por

$${\displaystyle \alpha ^{-1}=\operatorname {mex} (S),}$$donde S es el conjunto más pequeño de ordinales (números) tales que

1. 0 es un elemento de S ;
2. Si 0 < α ′ < α y β' es un elemento de S , entonces también es un elemento de S . ${\displaystyle {\tfrac {1+(\alpha '\oplus \alpha )\beta '}{\alpha '}}}$

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

Al igual que en el caso de la suma de números, existe un medio para calcular el producto de números de ordinales finitos. Este se determina mediante las reglas que

1. El producto numérico de una potencia de Fermat 2 (números de la forma 2 ^{2 n} ) con un número menor es igual a su producto ordinario;
2. El cuadrado numérico de una potencia de Fermat 2 x es igual a 3 x /2 según se evalúa bajo la multiplicación ordinaria de números naturales.

El cuerpo algebraicamente cerrado más pequeño de números es el conjunto de números menores que el ordinal ω ^{ω ω} , donde ω es el ordinal infinito más pequeño. De ello se deduce que, como número, ω ^{ω ω} es trascendental sobre el cuerpo. ^[5]

Tablas de suma y multiplicación

Las siguientes tablas muestran la suma y multiplicación entre los primeros 16 números.

Este subconjunto está cerrado bajo ambas operaciones, ya que 16 tiene la forma  2 ^{2 n} . (Si prefieres tablas de texto simples, están aquí ).

Adición de números (secuencia A003987 en la OEIS )
Esta es también la tabla de Cayley de Z ₂ ⁴ , o la tabla de operaciones XOR a nivel de bits . Las matrices pequeñas muestran los dígitos individuales de los números binarios.

Multiplicación de Nimber (secuencia A051775 en la OEIS )
Los elementos distintos de cero forman la tabla de Cayley de Z 15 . Las matrices pequeñas son matrices
binarias permutadas de Walsh .

Multiplicación de nimbers de potencias de dos (secuencia A223541 en la OEIS )
El cálculo de los productos nim de potencias de dos es un punto decisivo en el algoritmo recursivo de multiplicación de nimbers.

Véase también

• Número surrealista

Notas

1. Avances en juegos de computadora: 14.a Conferencia Internacional, ACG 2015, Leiden, Países Bajos, 1 al 3 de julio de 2015, artículos seleccionados revisados . Herik, Jaap van den, Plaat, Aske, Kosters, Walter. Cham. 2015-12-24. ISBN 978-3319279923.OCLC 933627646  .{{cite book}}: CS1 maint: falta la ubicación del editor ( enlace ) CS1 maint: otros ( enlace )
2. Anany., Levitin (2012). Introducción al diseño y análisis de algoritmos (3.ª ed.). Boston: Pearson. ISBN 9780132316811.OCLC 743298766  .
3. "Teoría de juegos imparciales" (PDF) . 3 de febrero de 2009.
4. Brown, Ezra ; Guy, Richard K. (2021). "2.5 Aritmética de Nim y álgebra de Nim". La unidad de la combinatoria . Vol. 36 de The Carus Mathematical Monographs (edición reimpresa). American Mathematical Society . pág. 35. ISBN 978-1-4704-6509-4.
5. Conway 1976, pág. 61.

Referencias

• Conway, John Horton (1976). Sobre números y juegos . Academic Press Inc. (Londres) Ltd.
• Lenstra, HW (1978). Multiplicación de Nim . Informe IHES/M/78/211. Instituto de Altos Estudios Científicos. hdl : 1887/2125.
• Schleicher, Dierk; Stoll, Michael (2004). "Introducción a los juegos y números de Conway". arXiv : math.DO/0410026 .que trata sobre juegos, números surrealistas y nimbers.