Un PAÍS de Palillos

El quinto desafío de EL PAÍS, lo presenta Fernando Corbalán, catedrático de matemáticas y subdirector de DivulgaMAT. Hay hasta las 00.00 horas del martes 19 de abril para presentar las soluciones. En esta ocasión el reto consta de dos preguntas. Las soluciones deben enviarse al correo problemamatematicas@gmail.com. Como esta semana hay dos preguntas habrá dos premios. 

Para aclarar cualquier duda y en atención también a nuestros lectores sordos incluimos por escrito el problema por escrito.

Presentamos dos juegos y se trata de encontrar qué estrategia ganadora tienen, esto es, el procedimiento para ganar siempre, por muy hábil que sea nuestro rival. La estrategia puede ser del jugador que mueve primero o del segundo, eso también hay que averiguarlo. Obviamente, si el primer jugador tiene estrategia ganadora, no la tendrá el segundo. Para ambos juegos formamos la palabra PAIS con palillos de la forma en que se ve la imagen de arriba o el vídeo.

Primer juego: Por turnos, cada jugador retira uno, dos o tres palillos del dibujo. Gana el que retira el último palillo, esto es, el que deja la mesa vacía.

Segundo juego: Por turnos, los jugadores retiran el número que quieran de palillos pero siempre de la misma letra cada vez (de la P, de la A, de la I o de la S). Gana también el que retira el último palillo.

Se trata, como decíamos de hallar la estrategia ganadora en ambos juegos (el modo de ganar seguro) precisando si la tiene el jugador que abre el juego o el segundo.


SOLUCIÓN:

Los juegos de esta semana, me han parecido uno de los retos más sencillos hasta el momento. La solución enviada seguramente se publique con retraso, ya sabéis me voy de vacaciones a la playa. 

PISTA: Hay que tener en cuenta sólo el número de palillos de cada letra.

Bueno una vez de vuelta de vacaciones, veamos la respuesta enviada. Pero antes vamos a comentar unas cuestiones.

Los juegos aquí propuestos, son variantes del juego egipcio NIM: Juego del NIM (Inglés).

Bien vamos ahora con la respuesta enviada:

Primero debemos darnos cuenta que no es importante la palabra escrita con palillos, si no el número de palillos que usamos para escribir cada letra. En nuestro caso:

$$\begin{matrix}{P}&{\textrm{5 Palillos}}\\{A}&{\textrm{5 Palillos}}\\{I}&{\textrm{4 Palillos}}\\{S}&{\textrm{5 Palillos }}\\{TOTAL}&{\textrm{19 Palillos }}\end{matrix}$$

PRIMER JUEGO:

Para este primer juego, basta ver que tenemos que hacer que nuestro adversario tenga 4 palillos en su último turno, así retire 1, 2 o 3 siempre retiraremos nosotros el último palillo.

Para ello la estrategia ganadora es para el primer jugador en jugar, y consiste en dejar al segundo jugador múltiplos de 4. Esto es, el primer jugador debe retirar 3 palillos cualesquiera, de forma que al segundo jugador le queden 16 palillos:

Tendremos entonces 3 casos:

a) Si el segundo jugador retira 1 palillo, en el segundo turno el primer jugador debe retirar otros 3
b) si el segundo jugador retira 2 palillos,  en el segundo turno el primer jugador debe retirar 2 palillos
c) si el segundo jugador retira 3 palillos,  en el segundo turno el primer jugador debe retirar 1 palillo

De tal forma que al principio del segundo turno del segundo jugador habrá siempre 12 palillos. Procedemos de la misma manera que en los tres casos anteriores, hasta que en el tercer turno el segundo jugador se encuentra 8 palillos. Por último volvemos a proceder de igual forma hasta que en el cuarto y último turno el segundo jugador se encuentra siempre con 4 palillos, por lo que retire los que retire, siempre gana el primer jugador.

Como caso general si tuviéramos n palillos, y podemos retirar entre 1 y m palillos, con m<n, bastará con dejar al jugador contrario múltiplos de (m + 1). Si n es múltiplo de (m+1), dejaremos que empiece el otro jugador, si no es múltiplo empezaremos nosotros, y dejaremos al otro jugador con un múltiplo de (m+1)

SEGUNDO JUEGO:

En este caso es como colocar los palillos en filas, y que se puedan retirar tantos palillos como se quiera pero sólo de una fila. Colocamos nuestro palillos:

$$\begin{matrix}{P}&{IIIII}\\{A}&{IIIII}\\{I}&{IIII}\\{S}&{IIIII}\end{matrix}$$

Lo primero que debemos hacer es escribir en base 2 el número de palillos que hay en cada fila. Colocamos tal como se ve abajo las cantidades en binaria una debajo de otras y sumamos cada una de las columnas en base 10. (En nuestro caso suman 403):

$$\frac{\begin{matrix}{P}&{IIIII}&{1}&{0}&{1}\\{A}&{IIIII}&{1}&{0}&{1}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{IIIII}&{1}&{0}&{1}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{4}&{0}&{3}\end{matrix}}$$


En este caso también el primero que empieza tiene estrategia ganadora. Para ganar cada vez que tenemos que quitar palillos, tenemos que conseguir que la suma de todas las columnas sea un número par o 0.

En esta caso tendremos que conseguir transformar la suma de la tercera columna (3) a 2 (porque sólo podemos quitar palillos de una sola fila). Luego bastará con quitar un palillo de cualquiera de las letras que contienen 5 palillos, quedando por ejemplo:

$$\frac{\begin{matrix}{P}&{IIII}&{1}&{0}&{0}\\{A}&{IIIII}&{1}&{0}&{1}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{IIIII}&{1}&{0}&{1}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{4}&{0}&{2}\end{matrix}}$$

Será ahora el turno del segundo jugador, quite los palillos que quite de cualquiera de las filas nunca podrá dejar todas las columnas con suma par, por lo que siempre dejara una o más columnas con suma impar que nosotros transformaremos a par. En nuestro caso por ejemplo imaginemos que el otro jugador decide quitar palillos de la cuarta fila.

Tendremos 5 casos:

a) quita 1 solo palillo:

$$\frac{\begin{matrix}{P}&{IIII}&{1}&{0}&{0}\\{A}&{IIIII}&{1}&{0}&{1}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{IIII}&{1}&{0}&{0}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{4}&{0}&{1}\end{matrix}}$$

Nos bastará con quitar un palillo de la segunda letra, para volver a tener todas las columnas con suma par:


$$\frac{\begin{matrix}{P}&{IIII}&{1}&{0}&{0}\\{A}&{IIII}&{1}&{0}&{0}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{IIII}&{1}&{0}&{0}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{4}&{0}&{0}\end{matrix}}$$


b) quita 2 palillos:

$$\frac{\begin{matrix}{P}&{IIII}&{1}&{0}&{0}\\{A}&{IIIII}&{1}&{0}&{1}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{III}&{0}&{1}&{1}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{3}&{1}&{2}\end{matrix}}$$

Nos bastará con quitar dos palillos en la primera letra o fila 1

$$\frac{\begin{matrix}{P}&{II}&{0}&{1}&{0}\\{A}&{IIIII}&{1}&{0}&{1}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{III}&{0}&{1}&{1}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{2}&{2}&{2}\end{matrix}}$$

c) quita 3 palillos:

$$\frac{\begin{matrix}{P}&{IIII}&{1}&{0}&{0}\\{A}&{IIIII}&{1}&{0}&{1}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{II}&{0}&{1}&{0}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{3}&{1}&{1}\end{matrix}}$$

Nos bastará con quitar 3 palillos en la fila 2:

$$\frac{\begin{matrix}{P}&{IIII}&{1}&{0}&{0}\\{A}&{II}&{0}&{1}&{0}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{II}&{0}&{1}&{0}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{2}&{2}&{0}\end{matrix}}$$

d) quita 4 palillos:

$$\frac{\begin{matrix}{P}&{IIII}&{1}&{0}&{0}\\{A}&{IIIII}&{1}&{0}&{1}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{I}&{0}&{0}&{1}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{3}&{0}&{2}\end{matrix}}$$

Nos bastará con todos los palillos de alguna de las filas que tienen 4:


$$\frac{\begin{matrix}{P}&{}&{0}&{0}&{0}\\{A}&{IIIII}&{1}&{0}&{1}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{I}&{0}&{0}&{1}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{2}&{0}&{2}\end{matrix}}$$

5) quita 5 palillos:

$$\frac{\begin{matrix}{P}&{IIII}&{1}&{0}&{0}\\{A}&{IIIII}&{1}&{0}&{1}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{}&{0}&{0}&{0}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{3}&{0}&{1}\end{matrix}}$$

Nos bastará con todos los palillos de la fila 2

$$\frac{\begin{matrix}{P}&{IIII}&{1}&{0}&{0}\\{A}&{}&{0}&{0}&{0}\\{I}&{IIII}&{1}&{0}&{0}\\{S}&{}&{0}&{0}&{0}\end{matrix}}{\begin{matrix}{TOTAL}&{}&{2}&{0}&{0}\end{matrix}}$$

Como vemos quita los palillos que quite, siempre se le puede volver a dejar una suma par. El procedimiento es el mismo para los turnos siguientes. La estrategia ganadora por tanto será hacer que nuestro rival tenga siempre una suma par en cada columna.

SOLUCIÓN "EL PAÍS": "Cómo ganar siempre a los palillos"


2 comentarios:

  1. La estrategia booleana para resolver el segundo problema sería:

    Pasamos el número de palillos de cada letra a binario. La situación inicial sería 5,5,4,5, que en binario sería: 101, 101, 100, 101.

    Si hacemos la operación XOR (or exclusivo) entre esos valores (equivalente al control de paridad del código) tendremos:
    XOR(101,101,100,101)=001.

    La estrategia ganadora consiste en siempre dejar 000 este resultado. Para ello, el primer movimiento sería quitar 1 de cualquiera de los grupos de 5 palillo. Con lo que quedaría: XOR(100,101,100,101)=000.

    Si tuviésemos, por ejemplo, 5,5,4,1: XOR(101,101,100,001)=101.

    Para dejar la situación 000, podíamos optar por cualquiera de estos movimiento:
    a: Quitar 5 del primer montón
    b: Quitar 5 del segundo montón. En ambos quedaría 5,4,1: XOR(101,100,001)=000
    c: Quitar 3 del tercer montón. Quedaría 5,5,1,1: XOR(101,101,001,001)=000

    ResponderEliminar
  2. Gracias rovber, como ves mi solución estaba en concordancia con la tuya ;)

    ResponderEliminar