🔬 Teoría Matemática de Sprouts
Sprouts es mucho más que un juego de dibujos: es un objeto matemático rico que conecta la teoría de grafos, la topología plana y la teoría combinatoria de juegos. Aquí analizamos sus propiedades con rigor matemático y las conectamos con ventajas estratégicas concretas.
📐 1. El invariante de vidas: el teorema central
El resultado fundamental de Sprouts se obtiene a través de un argumento de invariante. Definimos la "vida total" del sistema como la suma de vidas disponibles en todos los puntos.
$$L_{\text{total}} = \sum_{i=1}^{k} (3 - c_i)$$
donde \(k\) es el número total de puntos y \(c_i\) es el número de conexiones del punto \(i\)
Al inicio, con n puntos y 0 conexiones: \(L_0 = 3n\).
En cada movimiento, el jugador consume 2 vidas de los puntos conectados (1 por cada extremo de la curva) y añade un punto nuevo con 1 vida disponible (nace con 2 conexiones usadas, por tanto \(3 - 2 = 1\) vida libre). El cambio neto de vidas es:
$$\Delta L = -2 + 1 = -1 \quad \text{por movimiento}$$
Esto implica que \(L\) decrece en exactamente 1 en cada turno. La partida termina cuando no se pueden conectar puntos, es decir cuando la vida total restante ya no permite hacer ningún movimiento válido.
📊 2. Demostración de las cotas de movimientos
Del invariante de vidas se deducen directamente los límites del número de movimientos \(m\):
$$2n - 1 \leq m \leq 3n - 1$$
Cota superior (3n − 1): El juego termina cuando ningún punto puede conectarse. El caso extremo es cuando queda exactamente 1 vida total (un punto con 1 conexión disponible), pero ese punto no puede conectarse consigo mismo sin usar 2 vidas. La vida total inicial es \(3n\), y se reduce en 1 por turno, así que el máximo de turnos es cuando llegamos a 1 vida restante: \(3n - 1\) movimientos.
$$m_{\max} = 3n - 1 \iff L_{\text{final}} = 1$$
Cota inferior (2n − 1): En el caso más restrictivo topológicamente, cada movimiento "mata" al punto nuevo inmediatamente (usando su única vida restante en el siguiente turno). Esto fuerza el fin antes. El análisis del grafo planar implica que el juego debe durar al menos \(2n - 1\) movimientos.
$$m_{\min} = 2n - 1$$
🗺️ 3. Sprouts como grafo planar
En cada momento del juego, el tablero de Sprouts puede describirse como un grafo planar: los puntos son vértices, las curvas son aristas, y el plano en el que se dibuja garantiza que no hay cruces.
Usamos la fórmula de Euler para grafos planares:
$$V - E + F = 2$$
donde \(V\) = vértices, \(E\) = aristas, \(F\) = caras (incluyendo la cara exterior)
En Sprouts con \(n\) puntos iniciales y \(m\) movimientos realizados: el número de vértices es \(V = n + m\) (los \(n\) originales más el punto nuevo de cada movimiento). El número de aristas es \(E = m\) (una curva por movimiento, aunque cada curva tiene dos "mitades" separadas por el punto nuevo; para el análisis topológico contamos cada curva como 2 aristas). Sustituyendo en la fórmula de Euler:
$$(n + m) - 2m + F = 2 \implies F = m - n + 2$$
Esto es notable: el número de regiones del plano que crea el juego es exactamente \(m - n + 2\). A más movimientos, más regiones. Y más regiones significa más oportunidades de encerrar puntos en islas inaccesibles.
🎮 4. Teoría de juegos combinatorios
Sprouts es un juego combinatorio de información completa, sin azar, determinista y de suma cero. El marco matemático adecuado para analizarlo es la Teoría de Juegos de Sprague-Grundy.
En teoría de juegos combinatorios, a cada posición del juego \(P\) se le asigna un número de Grundy (o nimber) \(\mathcal{G}(P)\):
$$\mathcal{G}(P) = \text{mex}\left(\{\mathcal{G}(P') : P' \text{ es una posición alcanzable desde } P\}\right)$$
donde \(\text{mex}\) es el "mínimo excluido" (el menor entero no negativo que no está en el conjunto). Una posición tiene valor de Grundy 0 si y solo si es una posición perdedora para el jugador que la enfrenta (con juego perfecto del rival).
Si \(\mathcal{G}(P) \neq 0\), la posición es ganadora para el jugador al que le toca mover. La complejidad de Sprouts es que el número de posiciones crece exponencialmente con \(n\), por lo que el análisis completo se hace computacionalmente.
🔢 5. Análisis de paridad y predicción de resultado
El resultado de Sprouts depende de la paridad del total de movimientos. Definamos la clase de paridad de una posición:
$$\text{Gana J1 (Normal)} \iff m_{\text{total}} \equiv 1 \pmod{2} \text{ (impar)}$$
El análisis computacional (Lemoine, Malbos et al., 2007–2011) ha resuelto Sprouts para muchos valores de \(n\). La secuencia de ganadores (J1 o J2) con juego perfecto para n = 1, 2, 3, ... no es periódica simple pero tiene patrones. Los valores de \(n\) donde gana J2 son \(n \equiv 0 \pmod{6}\) o \(n \equiv 3 \pmod{6}\) para n normal, con excepciones para valores pequeños.
$$n \bmod 6 \in \{3, 4\} \implies \text{Gana J2 (patrón aproximado para } n \text{ grande)}$$
🌐 6. Topología: regiones y conectividad
El aspecto topológico más profundo de Sprouts es que el plano en que se juega no es simplemente conexo durante el juego. Cada curva que se dibuja puede encerrar regiones, creando "agujeros topológicos" que limitan qué conexiones son posibles.
Formalmente, si llamamos \(\mathcal{R}\) al conjunto de regiones abiertas del plano creadas por las curvas dibujadas, entonces una curva entre \(A\) y \(B\) es válida si y solo si existe una curva continua en \(\mathbb{R}^2 \setminus \mathcal{C}\) (donde \(\mathcal{C}\) son las curvas existentes) que conecte A con B y no pase por ningún punto existente.
El número de caras del grafo planar resultante (por la fórmula de Euler ya vista) determina cuántas regiones distintas existen. Dos puntos en regiones distintas no pueden conectarse sin cruzar una curva existente:
$$F(m) = m - n + 2 \implies \text{regiones jugables}(m) = F(m) - 1 = m - n + 1$$
(restamos 1 por la cara exterior infinita, que no es una región "jugable" en sí misma)
💡 7. Aplicación estratégica del análisis matemático
📐
Cuenta las regiones
Después de \(m\) movimientos hay \(m - n + 1\) regiones jugables. Si todas las regiones contienen 0 o 1 vida disponible, el juego termina pronto. Controla cuántas regiones activas quedan.
⚖️
El invariante como brújula
La vida total \(L = 3n - m\) te dice exactamente cuántos movimientos quedan como máximo. Si \(L = k\), quedan máximo \(k-1\) movimientos más. Úsalo para anticipar el final.
🏝️
Grundy de islas
Una isla con \(k\) vidas disponibles tiene número de Grundy relacionado con \(k\). Las islas con Grundy ≠ 0 son ganadores locales. Combínalas usando XOR de nimbers para la estrategia global.
🔮
Predicción de fin de juego
Si conoces el total de movimientos restantes \(r\), y \(r\) es impar, gana quien tiene el turno. Fuerza un \(r\) impar para ti haciendo jugadas que reduzcan (o no) el espacio.