En matemáticas , los números , también llamados números de Grundy , se introducen en la teoría de juegos combinatoria , donde se definen como los valores de 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 y la multiplicación ordinales .
Debido al teorema de Sprague-Grundy que establece que cada juego imparcial es equivalente a un montón de Nim de cierto tamaño, los números surgen en una clase mucho más grande de juegos imparciales. También pueden ocurrir en juegos partidistas como Domineering .
Las operaciones de suma 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, su suma numérica es menor que cualquiera de los sumandos. [1] La operación de exclusión mínima se aplica a conjuntos de números.
Nim es un juego en el que dos jugadores se turnan para retirar objetos de distintos montones. Como los movimientos dependen sólo 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 retire el último objeto. El número de un montón es simplemente el número de objetos en ese montón. Usando la suma nim, se puede calcular el número del juego en su conjunto. La estrategia ganadora es forzar el número del juego a 0 para el turno del oponente. [2]
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ó horizontal o verticalmente hasta que no se puedan colocar más fichas. El primer jugador que no pueda realizar un movimiento pierde. Como los movimientos posibles para ambos jugadores son los mismos, es un juego imparcial y puede tener un valor mayor. Por ejemplo, cualquier tablero que sea de tamaño par por tamaño par tendrá un número de 0. Cualquier tablero que sea par por impar tendrá un número distinto de cero. Cualquier tablero de 2 × n tendrá un número de 0 para todos los n pares y un número de 1 para todos los n impares .
En el juego de Northcott, las clavijas 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. Varias columnas se apilan juntas para agregar complejidad. Pierde el jugador que ya no puede realizar ningún movimiento. 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 disminúyelo en tu próximo movimiento. De lo contrario, juega el juego de Nim y haz que la suma Nim del número de espacios entre las fichas en cada fila sea 0. [3]
Hackenbush es un juego inventado por el matemático John Horton Conway . Se puede jugar en cualquier configuración de segmentos de línea coloreados 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 pueda analizarse utilizando números, eliminando la distinción de las líneas, permitiendo a cualquiera de los jugadores cortar cualquier rama. También se eliminan todos los segmentos que dependan 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 nim con un valor nimber. Además, todas las conexiones separadas a la línea de tierra también se pueden sumar para obtener un número del estado del juego.
La adición de Nimber (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
Para ordinales finitos, el nim-sum 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 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 por 0; el lugar de los ochos suma 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 generan una estrategia ganadora para Nim y sólo puede haber una estrategia de ese tipo; o se puede demostrar directamente por inducción: Sean α y β dos ordinales finitos, y supongamos que la suma mínima 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, se excluye α ⊕ β .
La suma de números es asociativa y conmutativa , con 0 como elemento de identidad aditivo . Además, un número es su propio inverso aditivo . [4] Se deduce que α ⊕ β = 0 si y sólo si α = β .
La multiplicación de Nimber ( nim-multiplicación ) se define recursivamente por
La multiplicación de números es asociativa y conmutativa, teniendo el ordinal 1 como elemento identidad multiplicativo . Además, la multiplicación de números se distribuye sobre la suma de números. [4]
Así, excepto por el hecho de que los números forman una clase propia y no un conjunto, la clase de números forma un anillo . De hecho, incluso determina un campo algebraicamente cerrado de característica 2, con el inverso multiplicativo número de un ordinal α distinto de cero dado por
Para todos los números naturales n , el conjunto de números menores que 2 2 n forman el campo 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 como n → ∞ de los cuerpos GF(2 2 n ) . Este subcampo no es algebraicamente cerrado, ya que ningún campo GF(2 k ) con k que no sea una potencia de 2 está contenido en ninguno de esos campos y, por lo tanto, no está en su límite directo; por ejemplo, el polinomio x 3 + x + 1 , que tiene una raíz en GF(2 3 ) , 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 una forma de calcular el producto de números de ordinales finitos. Esto está determinado por las reglas que
El campo algebraicamente cerrado de números más pequeño 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 campo. [5]
Las siguientes tablas muestran la suma y multiplicación entre los primeros 16 números.
Este subconjunto está cerrado en ambas operaciones, ya que 16 es de la forma 2 2 n . (Si prefiere tablas de texto simples, están aquí ).
![{\displaystyle {\begin{aligned}\alpha >\zeta \oplus \alpha &=\beta \oplus \gamma ,\\[4pt]\beta >\zeta \oplus \beta &=\alpha \oplus \gamma ; \end{alineado}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/523a3f6e9a1d7e9b5819cee91a8f732543f4d23b)
![{\displaystyle {\begin{aligned}(\beta \oplus \gamma )\oplus \beta ,\\[4pt]\alpha \oplus (\alpha \oplus \gamma );\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0cadaa34ad5b207bd5735cc8eba059997a4bfdd4)
{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ) Mantenimiento de CS1: otros ( enlace )