En matemáticas , el mex (" valor mínimo excluido ") 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 complementario .
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 a las que se puede llegar 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 eligen una numeración de los colores de vértices disponibles. Luego, consideran los vértices en orden, para cada vértice que elige su color como el valor mínimo excluido del conjunto de colores ya asignados a sus vecinos. [2]
Los siguientes ejemplos suponen que el conjunto dado es un subconjunto de la clase de números ordinales :
donde ω es el ordinal límite de los números naturales.
En la teoría de Sprague-Grundy, el ordinal mínimo excluido se utiliza para determinar el número de una partida imparcial de juego normal . En una partida de este tipo, cada jugador tiene los mismos movimientos en cada posición y el último jugador en mover gana. El número es igual a 0 para una partida que pierde inmediatamente el primer jugador, y es igual al mex de los números de todas las posiciones siguientes posibles para cualquier otra partida.
Por ejemplo, en una versión de una pila de Nim , el juego comienza con una pila de n piedras, y el jugador que va a mover 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 va a mover dejará 0 piedras, y mex({0}) = 1 , da el nimber para este caso. Si n son 2 piedras, el jugador que va a mover puede dejar 0 o 1 piedras, dando el nimber 2 como el mex de los nimbers {0, 1}. En general, el jugador que va a mover con una pila de n piedras puede dejar cualquier cantidad entre 0 y 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 número 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 una pila de Nim no es cero; el movimiento ganador es tomar todas las piedras.
Si cambiamos el juego de modo que el jugador que debe mover pueda tomar hasta 3 piedras solamente, entonces, con n = 4 piedras, los estados sucesores tienen nimbers {1, 2, 3}, lo que da un mex de 0. Como 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 nimbers de los estados sucesores de 2, 3 y 4 piedras son los nimbers 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.
Consulte nimbers para obtener más detalles sobre el significado de los valores nimber.
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7e8383687e070732685e59ae3ee912aef59e1da)