rompecabezas de prueba por contradicción

Question

Considere el siguiente juego entre dos jugadores:

- Hay una retícula de galletas inicialmente rectangular.

- La galleta de la esquina superior izquierda está envenenada.

- Los jugadores se turnan. En el turno de un jugador, éste debe comer alguna galleta junto con cada galleta a la derecha y/o debajo de ella. (Véase el diagrama para un ejemplo de movimiento legal).

- El jugador perdedor es el que se ve obligado a comer la galleta envenenada. 2

Demuestra que el jugador que va primero siempre puede ganar.

Aquí está mi prueba

A modo de contradicción, asuma que el jugador que va primero no siempre gana. Digamos que el primer jugador se come la galleta de abajo a la derecha en el primer intento (es decir, 4,5). Entonces en el siguiente turno el segundo jugador toma su turno y se come la galleta en el lugar (3,4). En la tercera ronda, el primer jugador se come la galleta en el lugar (2,3). Luego el segundo jugador se come la galleta en el lugar (1,2). Entonces el primer jugador toma su turno y cae en el lugar (1,1). Entonces pierde. Así que esto es una contradicción porque el segundo jugador puede forzar una victoria. Por lo tanto, la afirmación es siempre verdadera.

¿Puede alguien ayudarme en esto? Gracias de antemano

Answer 1

Supongamos que el segundo jugador (B) tiene una estrategia ganadora. Entonces debe tener una jugada ganadora, $M$ en el caso de que el primer jugador (A) se coma sólo la galleta inferior derecha en su primer movimiento. El resultado de la supuesta jugada ganadora de B en ese caso es que se ha comido un rectángulo de galletas. Pero A podría haberse comido ese mismo rectángulo de galletas en su primer movimiento, dejando a B en la misma posición (¡perdedora!) en la que está ahora A. Esto contradice la suposición de que B tiene una estrategia ganadora y $M$ fue una jugada ganadora. (Esto se llama un argumento de "robo de estrategia". Demuestra que A tiene una estrategia ganadora, pero no da ninguna pista sobre cuál podría ser).

Answer 2

En primer lugar, se trata de un juego finito de dos jugadores con información perfecta y sin empates. Por lo tanto, el primer jugador o el segundo deben tener una estrategia ganadora.

Supongamos, por el contrario, que el segundo jugador tiene una estrategia ganadora. La estrategia debe ser así :

• si el primer jugador toma $(a_1,b_1)$ entonces tomo $(x_1,y_1)$ ,

• si el primer jugador toma $(a_2,b_2)$ entonces tomo $(x_2,y_2)$ ,

  ...

• si el primer jugador toma $(a_N,b_N)$ entonces tomo $(x_N,y_N)$ .

• si el primer jugador toma $(1,1)$ entonces yo gano.

Dejemos que $f$ sea la función que describe esta estrategia: $$ f(a_1,b_1) = (x_1,y_1), \, \, f(a_2,b_2) = (x_2,y_2) , \,\, \cdots $$ Observe que

1. Según las reglas del juego, $a_1 \le x_1 , b_1 \le y_1$ y $a_1 + b_1 \le x_1 +y_1 - 1$ .
2. No hay $(a,b)$ tal que $f(a,b) = (1,1)$ . Porque en esta estrategia el segundo jugador siempre gana.

Así que considera la siguiente secuencia: $$ (n,m), f(n,m), f^{(2)}(n,m) , \cdots$$ Esta secuencia es finita ya que si $(a,b) = f^{(k)}(n,m)$ entonces $a+b \le n+m -k$ . Y debe terminar en $(1,1)$ porque si $(a,b) = f^{(n+m-2)}(n,m) $ entonces $a+b\le 2$ . Sin embargo, $(1,1)$ no puede ser a imagen y semejanza de $f$ ya que es una estrategia ganadora. Por lo tanto, tenemos una contradicción.