Juegos combinatorios para dos jugadores.
La Teoría de Juegos Combinatorios en el contexto de las olimpiadas de matemáticas trata principalmente sobre juegos imparciales. Estos son juegos de dos jugadores con información perfecta, sin elementos de azar (como dados) y con un número finito de movimientos, donde las jugadas disponibles dependen solo del estado del juego y no de qué jugador esté moviendo. El juego termina cuando un jugador ya no puede hacer un movimiento, y la convención estándar (Convención de Juego Normal) dice que el último jugador en mover gana o, lo que es lo mismo, el primer jugador que no puede mover pierde. La idea fundamental es clasificar cada estado del juego como una Posición Ganadora (posición N), desde la cual el Siguiente (Next) jugador en mover tiene una estrategia ganadora, o una Posición Perdedora (posición P), desde la cual el jugador Previo (Previous) ya ganó (lo que significa que el jugador actual está perdido si el oponente juega de forma óptima).
La lógica recursiva con la que definimos estas posiciones es simple pero poderosa: un estado es una posición P si cada movimiento posible lleva a una posición N, y un estado es una posición N si existe al menos un movimiento que lleve a una posición P. Aunque puedes resolver juegos simples yendo de atrás para adelante desde el estado final, los juegos complejos requieren que identifiques invariantes. El más famoso de estos es el Juego de Nim, donde la estrategia ganadora depende de la representación binaria del tamaño de los montones.
Para competencias más