Cross, Treble Cross
James Bond juega con el Dr. No a un juego para decidir si el Dr No le
revela su plan maestro para destruir el mundo. El tablero es una fila de
cuadraditos. Por turnos, cada jugador elige un cuadradito vacío y dibuja
una cruz. Gana el primer jugador que consiga conectar 3 cruces.
Un poco de estrategia
Hay movimientos que significan perder inmediatamente. Si dibujamos
una cruz pegada a otra, en el turno siguiente nuestro oponente hará 3 en
raya. Lo mismo pasa con dibujar una cruz dejando solo una casilla de
separación con la más próxima, pues nuestro oponente jugará entre ambas
y ganará. De esta forma, podemos pensar que cada cruz “bloquea” las
casillas que se encuentran a 1 ó 2 de distancia, pues suponen perder
inmediatamente. El juego se convierte así en uno de ir eliminando
casillas hasta que no quede ninguna (juega en la interfaz
pro).
Con este enfoque, podemos ver que el primer jugador siempre se puede
llevar la victoria cuando juega en un tablero impar. Esto es porque
puede empezar jugando en el centro, lo que dividirá el tablero en dos
tableros iguales más pequeñitos. De esta forma, por cada movimiento que
haga su oponente en un tablero, este podrá responder jugando el mismo
movimiento pero en el tablero opuesto. Esta estrategia de jugar en
“espejo” es muy habitual en este tipo de juegos.
Hasta donde yo sé, no se conoce una estrategia ganadora para un
tablero par 🤷♂️.
Todo cuenta
Parece que no podemos resolver complementamente el juego (yo al menos
no puedo). No podemos dar una estrategia ganadora para cualquier tablero
pero esto no va a frenar nuestras ganas de resolver problemas
combinatorios que nadie nos ha pedido. Vamos a contar. Dado un tablero
de tamaño n, en general no todas las partidas terminarán en el mismo
número de jugadas. Vamos a asumir la convención de la sección anterior
de que una partida consiste en ir quitando casillas. Podemos
preguntarnos entonces:
- ¿En cuántos movimientos termina la partida más
corta? Tras terminar la partida, estudiamos el tablero de
izquierda a derecha. Si la primera cruz no aparece en la tercera
casilla, podemos mover todas las cruces hacia la derecha hasta que esto
pase. Algunas cruces puede que se “salgan”, con lo que ese tablero
representará una partida que ha durado igual o menos jugadas. Razonamos
así para ver que hemos de ir colocando las cruces consecutivamente de
forma que estén separadas por 4 casillas (si hay dos más cerca, las
movemos todas hacia la derecha). Este tablero será uno de los que menos
cruces use, \(\lceil \frac{n}{5}
\rceil\) para ser exactos, pues cada cruz bloquea 5 casillas
contando la suya, a excepción de la última cruz que puede que bloquee
menos.
- ¿En cuántos movimientos termina la partida más
larga? Razonando como antes, vemos que una de las partidas que
consta del máximo número de movimientos es la que va alternando una cruz
y luego dos casillas, con lo que este número es \(\lceil \frac{n}{3} \rceil\) (cada cruz
bloquea sus dos casillas siguientes).
- ¿Cuántas partidas hay? Distinguimos dos partidas si
el tablero es el mismo al terminar. Llamaremos \(t_n\) al número de partidas en el tablero
de n casillas. La primera cruz puede estar desde en la primera casilla
hasta en la tercera (más allá de ahí querría decir que no es la primera
cruz). Si está en la primera, la segunda cruz podría estar a partir de
la cuarta casilla. Habrían entonces \(t_{n-3}\) formas de completar el tablero.
De la misma forma, si la primera cruz se encontrase en la segunda o
tercera casilla, podríamos completar el tablero de \(t_{n-4}\) ó \(t_{n-5}\) formas distintas,
respectivamente. Esto nos da la recurrencia \(t_n = t_{n-3} + t_{n-4} + t_{n-5}\), que
nos permite calcular este número de forma recursiva.
Como es gratis, adjunto una tabla con algunos de estos números
calculados y un trasto para calcular la columna deseada de la tabla.
Notas
- Este juego se llama Treblecross y es
del capítulo “Take and break” de Winning
Ways for your Mathematical Plays. Su notación octal es 007 (ver
esta explicación).
Este juego no aparece en ninguna película de James Bond, al menos que yo
sepa.
- En el momento de escribir esto, agosto de 2024, no se conoce si este
juego es periódico o no (Siegel, Capítulo 4: Juegos imparciales. Tras el
Teorema de periodicidad octal, sección sobre juegos de monedas). Algunos
(muchos) valores de su sucesión de NIM están calculados en las tablas de
juegos octales de Achim Flammenkamp.
- Por si quieres ver
los nim values mientras juegas.
- EDIT: para obtener una fórmula no recursiva del número de partidas
puede considerarse estudiar las raíces del polinomio característico (wikipedia).
Gracias a Alberto por esta observación.
- La sucesión \(t_n\) del número de
partidas es esta.