Solución: Juego con puntos

Publicamos la solución al divertimento Juego con puntos. Muchas gracias a Don Diedro y Don Pablo y Antonio Medinilla Garófano y David Ramos Orozco por las soluciones que nos han enviado.

Divertimento

Nuestros queridos Ana y Bernabé idean el siguiente juego: provistos cada uno de un lápiz que escribe con diferente color al del otro (los supondremos de colores rojo y negro), se divierten del siguiente modo:

Se construye un rectángulo de veinte puntos rojos alineados en cuatro filas de cinco puntos cada una y encima y debajo de cada una de esas filas se insertan cuatro puntos de color negro aprovechando las mitades de los espacios entre los puntos anteriores, tal como aparece en la siguiente figura:

Ana traza con su lápiz una línea vertical u horizontal que una entre sí dos puntos adyacentes de su propio color, elegido previamente. Después, Bernabé hace exactamente lo mismo uniendo dos puntos adyacentes del color que le corresponda. Van haciendo esto por turnos, y el objetivo de ambos es formar un camino continuo de segmentos uniendo puntos del mismo color que vaya desde la fila superior de puntos negros hasta la fila inferior de esos puntos, para uno de los jugadores, o desde la columna más a la izquierda de puntos rojos hasta la columna más a la derecha para el otro jugador.

Ese camino no tiene por qué ser recto, pues puede girar en cualquier dirección siempre y cuando una finalmente lados opuestos del tablero. Asimismo, cualquier jugador puede utilizar también sus líneas para bloquear el camino del otro jugador. Gana quien complete en primer lugar su camino.

¿Existe una estrategia ganadora para alguno de los dos jugadores? (No se la diremos a ninguno de los dos.)

Solución

Este juego se conoce en inglés como Bridg-It, aunque hay otras versiones. Existen pruebas constructivas de que Ana (la primera jugadora) posee una estrategia ganadora, usando teoría de grafos. Los lectores interesados pueden consultar el primer enlace o esta memoria.

Otra posibilidad, teniendo en cuenta el tamaño relativamente reducido del tablero, es atreverse con un enfoque directo basado en un análisis del mismo juego con tableros \(2\times 3\) y \(3\times 4\), como han seguido Don Diedro y Don Pablo. Dado que no hay muchas jugadas posibles, es fácil ver que en el primer caso es Ana quien puede ganar sin mucho problema, y algo difícil ver que ocurre lo mismo en el segundo caso.

Sin embargo, en esta entrada optaremos por dar una prueba no constructiva, válida para cualquier cantidad \(n \times (n+1)\) de puntos para cada jugador, siguiendo un razonamiento del tipo de robo de estrategia, que tan útil es para demostrar la existencia de estrategia ganadora en algunos juegos. A nosotros ya nos sirvió en el de la tableta de chocolate inversa. Es más, fue el gran John Nash quien utilizó esta técnica por primera vez para demostrar la existencia de estrategia ganadora para el juego Hex. No en vano, nuestro juego de los puntos es un caso particular del Hex, así que vamos a ello, siguiendo el argumento general para el Hex.

En primer lugar, hemos de ver que el juego no admite empates. En efecto, la única posibilidad que hay de que ni Ana ni Bernabé puedan ganar es que no puedan completar el camino de segmentos de un lado al otro del tablero. Tal situación solo es posible porque un segmento de un jugador bloquea el camino del contrario, y para poder bloquear todos los posibles segmentos es preciso trazar segmentos que bloqueen desde un extremo a otro del tablero, es decir, construir un camino de segmentos de lado a lado. En otras palabras, ganar el juego. Por tanto, si algún jugador no puede ganar es porque el otro ha ganado.

En general, en un juego de dos jugadores con intereses opuestos, en el que no se oculta información y hay una cantidad finita de movimientos posibles, que no depende del azar y se juega alternativamente, si no existe posibilidad de empate entonces debe haber una estrategia ganadora. Este enunciado se conoce como Teorema de Zermelo. Antonio Medinilla y David Ramos han demostrado rigurosamente la inexistencia de empates, lo que resuelve, gracias a dicho resultado, nuestra pregunta original. Nosotros seguiremos mostrando que además es Ana quien tiene las de ganar.

Supongamos pues que sea Bernabé quien tenga una estrategia ganadora. En ese caso, Ana debe trazar un segmento cualquiera, y adoptar el rol de Bernabé como segundo jugador, siguiendo dicha estrategia. Podría ocurrir que, siguiendo dicha estrategia, Ana debiera trazar justo el segmento que dibujó al principio. En ese caso, basta con trazar cualquier otro, nuevamente de forma arbitraria; si no pudiera trazar ninguno el juego habría terminado, y no cabe otra posibilidad que haya ganado Ana, puesto que está siguiendo una estrategia ganadora.

En conclusión, Ana siempre va a jugar la estrategia ganadora de Bernabé con un segmento más en el tablero. En este juego, tener un segmento más trazado nunca es una desventaja, en todo caso lo contrario. Por consiguiente, siguiendo la estrategia de Bernabé, Ana logrará ganar. Sin embargo, esto contradice el hecho de que sea Bernabé quien posea una estrategia ganadora, ya que él puede haberla seguido también. En conclusión, no existe tal estrategia, y como o Ana o Bernabé deben tenerla, no queda sino que sea Ana la afortunada.