México (matemáticas)

En matemáticas , el mex (valor mínimo excluido) de un subconjunto de un conjunto bien ordenado es el valor más pequeño del conjunto completo que no pertenece al subconjunto. Es decir, es el valor mínimo del conjunto complemento .

Más allá de los conjuntos, las subclases de clases bien ordenadas tienen valores excluidos mínimos. Los valores excluidos mínimos de las subclases de los números ordinales se utilizan en la teoría de juegos combinatoria para asignar valores nim a juegos imparciales . Según el teorema de Sprague-Grundy , el valor nim de una posición de juego es el valor excluido mínimo de la clase de valores de las posiciones que se pueden alcanzar en un solo movimiento desde la posición dada. ^{[ 1 ]}

Los valores mínimos excluidos también se utilizan en la teoría de grafos , en algoritmos de coloración voraz . Estos algoritmos suelen elegir un orden de los vértices de un grafo y una numeración de los colores disponibles para cada vértice. A continuación, consideran los vértices en orden, asignando a cada uno el color mínimo excluido del conjunto de colores ya asignados a sus vecinos. ^{[ 2 ]}

Los siguientes ejemplos presuponen que el conjunto dado es un subconjunto de la clase de números ordinales : $${\displaystyle {\begin{array}{lcl}\operatorname {mex} (\emptyset )&=&0\\[2pt]\operatorname {mex} (\{1,2,3\})&=&0\\[2pt]\operatorname {mex} (\{0,2,4,6,\ldots \})&=&1\\[2pt]\operatorname {mex} (\{0,1,4,7,12\})&=&2\\[2pt]\operatorname {mex} (\{0,1,2,3,\ldots \})&=&\omega \\[2pt]\operatorname {mex} (\{0,1,2,3,\ldots ,\omega \})&=&\omega +1\end{array}}}$$

donde ω es el ordinal límite para los números naturales.

En la teoría de Sprague-Grundy, el ordinal excluido mínimo se utiliza para determinar el número de un juego imparcial de juego normal . En dicho juego, ambos jugadores tienen los mismos movimientos en cada posición y gana el último jugador en mover. El número es igual a 0 para un juego que pierde inmediatamente el primer jugador, y es igual a la suma de los números de todas las posiciones siguientes posibles para cualquier otro juego.

Por ejemplo, en una versión de Nim de una sola pila , el juego comienza con una pila de n piedras, y el jugador que mueve puede tomar cualquier número positivo de piedras. Si n es cero piedras, el nimber es 0 porque el mex del conjunto vacío de movimientos legales es el nimber 0. Si n es 1 piedra, el jugador que mueve dejará 0 piedras, y mex({0}) = 1 , da el nimber para este caso. Si n es 2 piedras, el jugador que mueve puede dejar 0 o 1 piedras, dando el nimber 2 como el mex de los nimbers {0, 1}. En general, el jugador que mueve con una pila de n piedras puede dejar cualquier cantidad desde 0 hasta n − 1 piedras; el mex de los nimbers {0, 1, …, n − 1} es siempre el nimber n . El primer jugador gana en Nim si y solo si el nimber no es cero, por lo que de este análisis podemos concluir que el primer jugador gana si y solo si el número inicial de piedras en un juego de Nim de una pila no es cero; el movimiento ganador es tomar todas las piedras.

Si cambiamos el juego de modo que el jugador que mueve pueda tomar hasta 3 piedras solamente, entonces con n = 4 piedras, los estados sucesores tienen números {1, 2, 3}, lo que da un mex de 0. Como el número para 4 piedras es 0, el primer jugador pierde. La estrategia del segundo jugador es responder a cualquier movimiento que haga el primer jugador tomando el resto de las piedras. Para n = 5 piedras, los números de los estados sucesores de 2, 3 y 4 piedras son los números 2, 3 y 0 (como acabamos de calcular); el mex del conjunto de números {0, 2, 3} es el número 1, por lo que comenzar con 5 piedras en este juego es una victoria para el primer jugador.

Consulte nimbers para obtener más detalles sobre el significado de los valores nimber.