Aprende la magia y las matemáticas de cómo ganar juegos cuando tu oponente va primero.

La mayoría de los juegos que enfrentan a dos jugadores o equipos requieren que uno de ellos haga la primera jugada. Esto da como resultado una asimetría incorporada, y surge la pregunta: ¿Debería ir primero o segundo?

La mayoría de la gente instintivamente quiere ir primero, y esta intuición generalmente se confirma. En los juegos comunes de dos jugadores, como el ajedrez o el tenis , es una ventaja real, aunque modesta, "ganar el sorteo" e ir primero. Pero a veces te conviene dejar que tu oponente haga la primera jugada.

En nuestro acertijo Insights de febrero , presentamos cuatro situaciones dispares en las que, de manera contraria a la intuición, la obligación de mudarse es una desventaja grave y, a menudo, decisiva. En ajedrez, esto se conoce como zugzwang, una palabra alemana que significa "compulsión de movimiento". Veamos cómo se materializa la extraña magia del zugzwang en cada uno de nuestros cuatro escenarios.

Rompecabezas 1: Ajedrez
La posición en el tablero de ajedrez a continuación se alcanzó en el segundo juego del partido de Candidatos al Campeonato Mundial en 1971 entre el gran maestro estadounidense Bobby Fischer jugando con blancas y el gran maestro soviético Mark Taimanov jugando con negras. Es el turno de las negras de moverse, pero desafortunadamente las negras están en zugzwang y perderán. Nuestra tarea era explicar cómo.

(imagen 2)

Si comparamos las piezas menores, las blancas tienen un alfil y las negras un caballo. Ninguna de estas piezas es suficiente para forzar la victoria. Pero las blancas también tienen un peón que puede avanzar a la parte superior del tablero y convertirse en reina. Si eso sucede, las blancas ganan fácilmente. Así que la tarea de las negras es clara: Taimanov tiene que capturar el peón blanco, incluso si eso significa sacrificar su caballo para hacerlo. Eso conducirá a un empate, que es lo mejor que pueden hacer las negras aquí.

Al principio, podría parecer que el caballo de las negras está en una buena posición para capturar el peón de las blancas. El caballo está protegido por el rey negro y controla la casilla h7, por la que debe pasar el peón blanco antes de poder coronar.

Por desgracia, ahora la "compulsión de movimiento" de zugzwang asoma su fea cabeza. Porque aunque Taimanov se habría contentado con mantener su caballo en g5, se encuentra en la desafortunada posición de tener que mover su rey o el caballo. Si mueve su rey, ya no puede proteger al caballo, y el caballo muere, dejando al peón libre para avanzar. Si, por otro lado, mueve el caballo a la única casilla segura, f3, y luego las blancas empujan su peón a h6, es cierto que las negras pueden mover el caballo de vuelta a g5 en el siguiente movimiento. Esto evita que Fischer avance inmediatamente su peón a h7. Pero ahora las blancas pueden sacar el arma secreta del zugzwang en el ajedrez: pueden hacer un movimiento de "espera", deslizando su rey hacia g6. Una vez más, las negras deben moverse, y ahora Taimanov realmente se ha quedado sin opciones viables.

(Imagen 3)

Si las negras mueven su rey, su caballo cae. Si mueve su caballo a f3, el peón de las blancas avanza a h7 y se acaba el juego. (Si mueve su caballo a cualquier otro lugar, el alfil o el rey de las blancas lo capturarán y también se acabará el juego). Este es el poder del zugzwang en pocas palabras.

No hace falta decir que Fischer ganó el juego. Luego atrapó a Taimanov en un zugzwang aún más complicado en el juego 4 y finalmente barrió los partidos 6-0. Fischer aplastó a otros dos grandes maestros importantes antes de vencer al gran maestro soviético Boris Spassky en 1972 para convertirse en campeón mundial, en lo que se denominó el " partido del siglo ".

Varios lectores describieron soluciones a este problema.

Rompecabezas 2: Nim
En esta variación del antiguo juego Nim , dos jugadores, A y B, juegan un juego de resta en el que B elige un número inicial, del cual cada jugador resta un número pequeño hasta llegar a cero. Durante cada turno, un jugador debe restar al menos 1, hasta un máximo de 1 más que el dígito de las decenas del número actual. Así, si el número actual está entre 90 y 99, pueden restar cualquier número hasta el 10 inclusive; si es 80 a 89, pueden restar 1 a 9, y así sucesivamente. Finalmente, cuando el número restante esté entre 1 y 9, solo podrán restar 1 en cada turno. A va primero y B puede elegir un número inicial entre 90 y 99. El jugador que se quedó haciendo la última resta pierde.

Pregunta: ¿Qué número inicial debería elegir B? ¿Puedes enumerar toda la escalera de zugzwang?

Este rompecabezas fue resuelto por los lectores Seth Cohen y Sunil Nandella . No puedo hacer nada mejor que citar la excelente explicación de Seth Cohen:

Para el Rompecabezas 2, comience desde abajo.
– Si A está en 1, A pierde. Asimismo, como en los dígitos simples solo pueden restar 1, A pierde en 3, 5, 7 y 9 (sumando 2 cada vez).
– Pero A no pierde con el 11, porque en el 11, A puede restar 2 y darle el 9 perdedor a B. Sin embargo, A pierde con el 12. A también pierde en 15 y 18 (suma 3 cada vez).
– Ahora, cuando saltamos a los 20, ya no podemos sumar 3, porque en 21, A puede restar 3 y darle el 18 perdido a B. Debemos sumar 4: 22, 26.
– Cuando saltamos a los 30 , tenemos que sumar 5: 31, 36.
– A los 40, sumar 6: 42, 48.
– Y así sucesivamente: cada vez que pasamos a una década superior, tenemos que sumar 1 más para continuar en la escalera de zugzwang .
– Toda la escalera de zugzwang, de arriba a abajo: 93, 82, 72, 63, 55, 48, 42, 36, 31, 26, 22, 18, 15, 12, 9, 7, 5, 3, 1.

Rompecabezas 3: Sim
Sim es un juego entre dos jugadores, llamémoslos rojo y azul. El juego se juega sobre la figura que se muestra, que consta de seis puntos, cada uno de los cuales se muestra unido entre sí por líneas negras (llamadas aristas en  teoría de grafos ). Cada jugador, a su vez, colorea un solo borde rojo o azul según su nombre. Si el movimiento de un jugador hace que tres de los puntos se unan con bordes del mismo color, el jugador pierde.

(Imagen 3)

Pregunta: ¿Puede describir el juego de Sim más corto posible que resulte en una posición de zugzwang recíproco (el jugador que se mueva a continuación pierde)? Enumere los movimientos realizados en el juego en secuencia.

Aquí hay una posición Sim en la que se alcanza la posición recíproca de zugzwang en nueve movimientos.

(Imagen 4)

Una orden de movimiento que podría generar esta posición es AB , BE , AC , CE , AD , DE , AF , FE , AE . Eso deja seis bordes restantes sin color: BC, BD, BF, CD, CF y DF. Colorear cualquiera de ellos de rojo o azul obliga a un triángulo a tener todos los bordes del mismo color, como se muestra en la siguiente tabla.

Por lo tanto, el jugador que tenga que moverse a continuación (en este caso, el jugador azul) estará en zugzwang y perderá. Para entender cómo llegamos a esta posición, considera el cuadrilátero formado por los cuatro puntos ABCE. Tiene dos bordes rojos contiguos, AB y AC, y dos bordes azules contiguos, BE y CE. Entonces, cualquiera que sea el color del borde BC (la diagonal del cuadrilátero), completará un triángulo del mismo color. Puede pensar en un conjunto de cuatro puntos con un borde faltante como una sola "unidad de zugzwang". Hay seis unidades de este tipo en esta posición, cada una condenando uno de los seis bordes sin color.

Azul llegó a esta situación temprano en el juego debido a un juego imperfecto. Como mencioné en la columna de rompecabezas , una estrategia ganadora siempre está disponible para el segundo jugador en Sim, sin importar lo que haga el primer jugador. La estrategia es evitar la creación de cuadriláteros de zugzwang, excepto dos que dejan un borde común sin colorear. Hay exactamente "6 elige 2" (o 15) bordes en el diagrama, por lo que el movimiento 15 (último) siempre recaerá en el primer jugador. teoría ramseynos dice que con seis puntas habrá un mínimo de dos triángulos con aristas todas del mismo color. Con un juego perfecto, el segundo jugador debería poder posponer la creación de triángulos unicolores hasta el último movimiento. Esto atrapará al primer jugador para que forme dos triángulos unicolores con el último borde.

El lector sunil nandella describió y dibujó la posición de un juego tan perfectamente jugado en el que la situación de zugzwang recíproco tiene lugar en el movimiento 15, lo que hace que el primer jugador pierda al producir inevitablemente los dos triángulos unicolores necesarios. Los dos cuadriláteros de zugzwang en la solución de nandella son BCEF y ABDE, ambos tienen BE como última arista sin color.

Rompecabezas 4: Pizza
Dos jugadores, A y B, comparten una pizza. A elige la primera porción y B corta la pizza. B debe cortar la pizza en rebanadas radiales en forma de cuña, haciendo cualquier cantidad de rebanadas que no necesitan ser todas del mismo tamaño. A puede elegir cualquier primer corte. Después de eso, B y A toman cada uno una porción por turno, eligiendo siempre una de las dos rebanadas que bordean la parte abierta de la pizza. Tanto A como B hacen todo lo posible para obtener la mayor cantidad posible de pizza.

Preguntas:

¿Cómo puede B cortar la pizza de tal manera que después de tomar todas las rebanadas, B tenga más pizza que A? Proporcione el número más pequeño posible de rebanadas en las que esto puede suceder y el tamaño relativo de cada rebanada.
¿Cuál es la fracción más grande de la pizza que B puede obtener?
¿Puede especificar todos los números posibles de cortes que no funcionarán para lograr este resultado?
Antes de describir las soluciones, repasemos algunas ideas heurísticas que nos pueden llevar a las respuestas. Como señaló Jack Latta , B nunca puede obtener una porción más grande de pizza si hay un número par de rebanadas. Para entender por qué, supongamos que la pizza tiene ocho rebanadas, numeradas del 1 al 8. Ahora, la pizza se puede dividir conceptualmente en dos porciones: las rebanadas impares O (rebanadas 1, 3, 5, 7) y las rebanadas pares. E (rebanadas 2, 4, 6, 8). El jugador A puede asegurarse de obtener E o O , el que sea mayor. Si Oes la porción más grande, A puede comenzar con la rebanada 1, dejando que B elija la rebanada 2 u 8; Luego, A puede continuar eligiendo la porción impar que está expuesta (ya sea 3 o 7 en el próximo turno) sin importar qué porción elija B. Esto siempre deja a B con opciones pares. Por el contrario, si E es más grande, A puede ganar obteniendo todas las rebanadas pares. Si ambas porciones son exactamente iguales, A puede escoger par o impar, negándole a B una parte más grande de la pizza. Entonces, la pizza que buscamos debe tener un número impar de rebanadas.

Una vez más, entra en juego el concepto de escaleras zugzwang (a las que me referiré como escaleras z). Como describí en el rompecabezas , si tienes una fila lineal de un número impar de rebanadas con tamaños alternos 1 y 3, el jugador que va primero debe "abrir" la escalera, cediendo todas las piezas más grandes al segundo jugador, quien por lo tanto ganar.

La dificultad es que, con una pizza redonda, A puede elegir primero un trozo grande. ¿Qué sucede entonces con la escalera z? Consideremos lo que sucede cuando una pizza consta de una única escalera en z de siete rebanadas 1, 3, 1, 3, 1, 3, 1, como se muestra en la siguiente figura, que tiene números de rebanada en gris y tamaños en marrón.

(Imagen 5)

Es útil distinguir entre el segmento 4, al que llamaremos segmento central, y los segmentos 2 y 6, que son los segmentos laterales. Si A toma el segmento central grande 4, nos quedan dos escaleras en z unidas de tamaños de segmento 1, 3, 1 (números de segmento 1-3 y 5-7). B está obligado a abrir uno de ellos (ella decide cuál) tomando la rebanada 3 o 5, cediendo otra pieza grande a A. Después de que se agote la escalera abierta, es el turno de A y está obligado a abrir la última escalera, cediendo la última pieza grande a B. Entonces, en este escenario, A obtiene dos rebanadas grandes y B obtiene una. Si, por otro lado, A opta por una de las rebanadas laterales grandes (rebanada 2 o 6), nos quedamos con una escalera en z de cinco rebanadas y una sola pieza pequeña, que B puede tomar, lo que obliga a A a abrir la escalera de cinco rebanadas y dé dos rebanadas grandes a B. En el caso de una pizza de cinco rebanadas en forma de z,

Todavía no tenemos una solución, pero hemos recopilado varias ideas que nos llevarán allí. Estos son:

Idea 1: La pizza debe tener un número impar de piezas.

Insight 2: Una escalera en z no funcionará. Según la idea 1 y el hecho de que las escaleras z tienen un número impar de cortes, necesitaríamos al menos tres escaleras z unidas.

Idea 3: Solo puedes mirar las porciones grandes. B debe conseguir más de ellos.

Idea 4: Si bien A tiene la ventaja de tomar la primera porción grande en una escalera z, necesita tomar la porción grande del medio, o perderá su ventaja. Si no hay un segmento grande intermedio (como en una escalera z de cinco o nueve segmentos con dos y cuatro segmentos grandes, respectivamente), los segmentos grandes se comparten.

Idea 5: cuando quedan dos escaleras z, el que sigue tiene la ventaja de decidir qué escalera abrir, lo que obliga al otro jugador a abrir la última. En una pizza con un número impar de piezas, el jugador que tiene esta elección clave siempre será B. ¡Esta idea es de oro!

Al lector witzar se le ocurrió una brillante solución de 21 segmentos que consiste en tres escaleras en z de longitudes de 5, 7 y 9 segmentos que ilustran muy bien estas ideas. La pizza tiene nueve rebanadas grandes y las escaleras tienen dos, tres y cuatro rebanadas grandes, respectivamente. En la siguiente figura, las tres escaleras z se muestran delimitadas por diferentes colores.

En lo que sigue, tenga en cuenta que debido a que A toma el primer corte y los jugadores se alternan a partir de entonces, A siempre juega en turnos impares y B en turnos pares.

(Imagen 7)

Si A toma su primera rebanada grande de la escalera z de cinco rebanadas, los dos jugadores dividen las dos rebanadas grandes y luego B puede abrir la escalera de siete rebanadas en el turno 6, dándole a A tres rebanadas grandes, mientras que B obtiene las cuatro rebanadas grandes. rebanadas de la escalera final de nueve rebanadas, que A se ve obligado a abrir en el turno 13. B gana con cinco rebanadas grandes contra las cuatro de A.

Si la primera rebanada de A es la rebanada grande del medio de la escalera de siete rebanadas, A obtiene dos de las tres rebanadas grandes de esa escalera. Luego, B abre la escalera de cinco rebanadas en el turno 8, cediendo sus dos rebanadas grandes a A mientras nuevamente toma todas las rebanadas grandes de la escalera de nueve rebanadas; como antes, A se ve obligado a abrir esta escalera en el turno 13. B gana nuevamente con cinco rebanadas grandes a las cuatro de A.

Si la primera rebanada de A es una de las grandes rebanadas centrales de la escalera de nueve rebanadas, A y B compartirán las cuatro rebanadas grandes de esta escalera por igual, y cada uno obtendrá dos. Esto sucede porque en el turno 5, A está obligado a abrir la pieza de 5 rebanadas que queda de esta escalera a B. Luego, como antes, B abre la escalera más pequeña de cinco rebanadas después de terminar la primera escalera, esta vez en el turno 10 Luego obtiene todas las rebanadas grandes en la última escalera de siete rebanadas, que A se ve obligada a abrir en el turno 15. Una vez más, B obtiene cinco rebanadas grandes por las cuatro de A.

Tenga en cuenta que si A busca una pequeña porción en su primer turno, simplemente le da a B porciones grandes de la primera escalera z de inmediato, sin cambiar la ventaja estratégica que tiene B cuando quedan dos escaleras z. Los resultados de A terminan siendo tan malos o peores que los casos anteriores. Lo mismo sucede si A no continúa hasta el final de una escalera sino que salta a una que no está abierta. En resumen, A está en zugzwang desde el principio y no tiene forma de ganar.

Está claro que 5/9 es la fracción más grande de una pizza de este tipo que B puede obtener si solo importan las porciones grandes. Esto supone que las porciones pequeñas son realmente pequeñas, las porciones grandes son mucho más de tres veces las pequeñas y A juega de manera óptima. Así, cinco novenos es la respuesta a nuestra segunda pregunta.

Resulta que el número más pequeño de porciones que permite que B gane es 15, que es la respuesta a nuestra primera pregunta. Esta pizza consta de tres escaleras zugzwang de cinco rebanadas cada una, con dos tipos de rebanadas grandes: grande ( l ) y extra grande ( L ). Una plantilla general para los tamaños de rebanadas en esta pizza es: s, l, s, l, s, s, L, s, L, s, s, l, s, L, s , donde srepresenta los segmentos pequeños (que se muestran en la figura con las tres escalas z de cinco segmentos marcadas). Los tamaños posibles de las 15 rebanadas para una pizza real podrían ser: 1, 3, 1, 3, 1, 1, 6, 1, 6, 1, 1, 3, 1, 6, 1. Puedes jugar con tal pizza y verifique que B obtenga la porción más grande sin importar qué porción elija A primero asegurándose de que obtendrá las porciones grandes o extragrandes de la más pesada de las otras dos escaleras en z al final.

(Imagen 8)

Con tal pizza, B obtendrá dos rebanadas L extragrandes y una rebanada l o una L y tres rebanadas l , dependiendo de lo que haga A en el turno 3. La proporción óptima entre l y L ocurre cuando ambas B son posibles. los ingresos anteriores son iguales, es decir, 2 L + l = L + 3 l , o L = 2 l . El tamaño máximo de la porción para B es (2 L + l )/(3 L + 3 l), que es 5/9, como antes. Resulta que ningún arreglo de rebanadas le permitirá a B obtener más de las cinco novenas partes de la pizza, suponiendo que A haga el mejor juego.

Puede rellenar la pizza anterior de 15 rebanadas con un número par de rebanadas pequeñas adicionales entre cualquiera de las escalas z, por lo que la solución anterior se puede generalizar a pizzas con cualquier número impar de rebanadas por encima de 15. Entonces, la respuesta a nuestra tercera La pregunta es que B no puede ganar si la pizza tiene un número par de rebanadas o un número impar de rebanadas menos de 15.

Felicitaciones a witzar por la brillante solución a este difícil problema de pizza zugzwang y por ganar el premio Insights de este mes. Gracias a todos los que contribuyeron.

Nos vemos pronto para nuevas ideas.

Corrección: 9 de abril de 2022
Esta solución de rompecabezas anteriormente se refería a una pizza de 15 rebanadas como si tuviera 21 rebanadas. El error ha sido corregido.