Dos jugadores colocando monedas en una mesa redonda con el objetivo de hacer el último movimiento

Question

Me encontré con este acertijo durante una entrevista de trabajo y pensé que valía la pena compartirlo con la comunidad porque me pareció ingenioso:

Supongamos que estás sentado en una mesa perfectamente redonda con un adversario a punto de jugar un juego. Al lado de cada uno de ustedes hay una bolsa infinitamente grande de centavos. El objetivo del juego es ser el jugador que pueda colocar el último centavo en la mesa. Los centavos no se pueden mover una vez colocados y no se pueden apilar unos sobre otros; además, los jugadores colocan 1 centavo por turno. Hay una estrategia para ganar este juego todas las veces. ¿Te mueves primero o segundo, y cuál es tu estrategia?

JMoravitz ha proporcionado la respuesta (oculta en spoilers) a continuación en caso de que estés frustrado!

Answer 1

Sí, ya he visto este antes. Asumiendo que se permite colocar exactamente una moneda por turno:

Ve primero y coloca una moneda en el centro del tablero. A partir de ese momento, cualquier movimiento que haga tu oponente, coloca una moneda en la ubicación opuesta en el espejo (es decir, rotada 180 grados). Es lógico que si el movimiento de tu oponente fue válido, el tuyo también lo será. Por lo tanto, siempre tendrás un movimiento disponible si tu oponente también lo tiene. Dado que el tamaño del tablero es finito, solo puede haber un número finito de turnos, por lo tanto, eventualmente ganarás.

Una prueba más completa:

Supongamos que el tablero se describe utilizando coordenadas polares con el centro del tablero como el origen ($r=0$).

Mi primer movimiento es colocar en $r=0$. Cuando mi oponente hace un movimiento legal en $(r,\theta)$, intento colocar una moneda en $(r,\theta+180^\circ)$.

Afirmación: Siempre se me permite hacerlo y dicho movimiento siempre será válido.

Prueba: Supongamos lo contrario. Eso implica que la ubicación objetivo no está en el tablero (en cuyo caso el movimiento anterior de mi oponente tampoco habría estado en el tablero y por lo tanto también fue inválido), o que la ubicación objetivo tendría una superposición de monedas con otra moneda colocada previamente. Como no podría haber sido la moneda que mi oponente acababa de colocar en su último turno (ya que está a $180^\circ$ de distancia), eso implica que esas monedas deben haber sido colocadas previamente. Sin embargo... dado que mis movimientos siempre están jugando $180^\circ$ opuestos a los de mi oponente, eso implica que debería haber la misma situación en el otro lado del tablero y que la moneda de mi oponente también se superpone con las monedas reflejadas correspondientes y por lo tanto el movimiento de mi oponente fue inválido. De cualquier manera, llegamos a una contradicción que implica que si el movimiento de mi oponente fue válido, mi movimiento también está garantizado para ser válido.

Answer 2

JMoravitz tiene una excelente publicación. Me alegra haber llegado a la misma respuesta, y me gustaría compartir un pensamiento que ayudó en mi proceso. Considera un caso extremo para averiguar si ir primero o segundo:

El problema especifica centavos y una mesa circular. Si hay una estrategia ganadora, entonces sin pérdida de generalidad, deberíamos ganar independientemente del radio de la mesa. Dada una mesa cuyo radio es más pequeño que el centavo, y asumiendo que al menos un centavo cabría en la mesa, claramente querrás ir primero. Ganarías inmediatamente.

¿Qué pasa si la mesa fuera... bueno... normal? ¿Cómo asegurar tu victoria? No te quedes sin opciones, por supuesto. Es la misma idea que la de J en la otra respuesta.

Dada la naturaleza centro-simétrica del arreglo, después de centrar tu centavo original, el jugador dos puede ser imitado hasta el final del juego. Por cada centavo que el oponente coloque en $(x,y)$, coloca tu próximo en $(-x,-y)$. Esperaría que la mayoría de los oponentes renuncien después de uno o dos turnos, o sufran una derrota lenta y triste.

Zugzwang después del movimiento 1 en realidad.

Answer 3

Estoy preguntándome si sería posible demostrar que la siguiente solución es una estrategia ganadora o perdedora:

Ve primero y coloca una moneda cerca del borde de la mesa de modo que no haya espacio para otra moneda en el exterior de esta.

Answer 4

Actualización: el OP cambió las reglas en revisión 3.

Mi intento como spoiler a continuación.

Me muevo primero y cubro toda la mesa con centavos.