En matemáticas, el mex de un subconjunto de un conjunto bien ordenado es el valor más pequeño de todo el conjunto que no pertenece al subconjunto. Es decir, es el valor mínimo del conjunto complemento . El nombre "mex" es una abreviatura de valor " mínimo excluido " .
Más allá de los conjuntos, las subclases de clases bien ordenadas tienen valores mínimos excluidos. Los valores mínimos excluidos de las subclases de los números ordinales se utilizan en la teoría de juegos combinatorios 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 mínimo excluido 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 codiciosos . Estos algoritmos normalmente eligen un orden de los vértices de un gráfico y eligen una numeración de los colores de vértice disponibles. Luego consideran los vértices en orden, para que cada vértice elija su color como el valor mínimo excluido del conjunto de colores ya asignado a sus vecinos. [2]
En la teoría de Sprague-Grundy, el ordinal mínimo excluido se utiliza para determinar el número de un juego imparcial de juego normal . En tal juego, cualquiera de los jugadores tiene los mismos movimientos en cada posición y el último jugador en moverse gana. El nimber es igual a 0 para un juego que el primer jugador pierde inmediatamente, y es igual al mex de los nimbers de todas las siguientes posiciones posibles para cualquier otro juego.
Por ejemplo, en una versión de Nim de una pila , el juego comienza con una pila de n piedras, y el jugador que se 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 a mover dejará 0 piedras, y mex({0}) = 1 , da el número para este caso. Si n son 2 piedras, el jugador a mover puede dejar 0 o 1 piedras, dando el nimber 2 como mex de los nimbers {0, 1} . En general, el jugador que se mueva con una pila de n piedras puede dejar entre 0 y n −1 piedras; el mex de los nimbers{0, 1, …, n −1} es siempre el número n . El primer jugador gana en Nim si y solo si el nimber no es cero, por lo que a partir 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 para que el jugador que se mueva pueda tomar hasta 3 piedras solamente, entonces con n = 4 piedras, los estados sucesores tienen nimbers {1, 2, 3} , dando un mex de 0. Dado que el nimber 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 nimbers {0, 2, 3} es el nimber 1, por lo que comenzar con 5 piedras en este juego es una victoria para el primer jugador.