La solución
que se da aquí se aplica para una modalidad distinta de la que
se planteó. En lo que sigue se sigue la regla de que el que retira
la última cerilla es el que gana, en lugar de ser el que pierde
(como se decía en el enunciado). En realidad, la idea de la solución
es la misma. Al final se incluye una carta de José H. Nieto en
la que se explica cómo aplicar esta solución al caso en el que
el que quita la última cerilla pierde.
Yo tenía una respuesta
a este problema, pero la que envió Pere Martir Antón Maynade es
más completa de lo que yo esperaba, así que aquí está:
"El problema que
se plantea tiene una formulación aún más general.
Se trata del mismo
juego pero sin ninguna limitación en cuanto a cerillas, o sea
que realmente se pueden tomar cuantas filas de cerillas se quieran
y cuantas cerillas en cada fila, que el método para ganar es
siempre el mismo. El juego, o como mínimo la versión que yo
conozco se llama NIM y creo que viene de los antiguos Egipcios,
que ya encontraron las solución ideal para ganar.
El jugador que siempre
gana es el que sigue este algoritmo:
Una vez escogida la
disposición de las cerillas, se transforman el número de cerillas
de cada fila a binario y se disponen en una sola columna. Si
seguimos el ejemplo del juego 7-5-3 seria así:
3 cerillas -- 011
5 cerillas -- 101
7 cerillas -- 111
Ahora lo que tiene que hacer el
primer jugador es sumar cada columna de números cuantos 1's
contiene y debe retirar tantas cerillas como sea necesario para
conseguir que el numero de 1's en cada columna sea par.
011 (3)
101 (5)
111 (7)
--------
223 (no cada cifra es par)
En este caso, debería retirar una cerilla
de cualquier fila (por ej. la 3), y así quedaría :
011 (3)
101 (5)
110 (6)
---------
222 donde cada cifra es par
La gracia del truco está en que:
1) desde una posición de cifras impares
se puede alcanzar un número par de 1's en cada columna
2) una vez estamos
en una situación par de 1's en cada columna es imposible quitar
cerillas de una fila y mantener esa distribución.
De esta manera cada vez que le toca
retirar cerillas al segundo jugador se encuentra con que debe
volver a un esquema de cerillas impares por columnas, y el primer
jugador puede volver al esquema par por columnas hasta llegar
por ejemplo a una situación tal que así:
1 cerilla ----->
001
0 cerillas-----> 000
1 cerilla -----> 001
(esquema par) ,en donde
el jugador 2 debe quitar una y con lo que el jugador 1 ya ha
ganado.
Vamos a dar una posible partida del
7-5-3 siguiendo este organigrama:
3 cerillas -----> 011
5 cerillas -----> 101
7 cerillas -----> 111
------
223 |
3) El primer
jugador debe restablecer el esquema par y por tanto puede
por ejemplo quitar 4 cerillas de la 3 fila.
3 cerillas ------> 011
1 cerilla -------> 001
2 cerillas ------> 010
-----
022 (pares) |
1) El jugador
1 quita 1 cerillas de
la fila 3
3 cerillas
-------> 011
5 cerillas
-------> 101
6 cerillas
-------> 110
------
222 (pares) |
4) El jugador
2 quita 1 cerillas
de la fila 1
2 cerillas ------> 010
1 cerilla ------> 001
2 cerillas ------> 010
-----
021 (impares) |
2) El segundo
jugador quita 4 cerillas de la fila 2 (por ejemplo, podría
hacer cualquier otra cosa)
3 cerillas ------> 011
1 cerilla -------> 001
6 cerillas ------> 110
------
122 |
5) el jugador
1 quita 1 cerilla
de la fila 2
2 cerillas ------> 010
0 cerillas ------> 000
2 cerillas ------> 010
-----
020 (pares) |
Desde aquí el jugador
1 solo debe igualar la fila que no toque el jugador 2 y ya gana.
El truco esta en que
una vez un jugador se coloca en un esquema de cerillas par por
columnas, ya no hay manera de que el otro pueda arrebatárselo.
En una situación idílica,
en la que los dos jugadores supieran el truco, ganaría aquel
jugador que pudiera acceder a un esquema par de cerillas por
columnas. Este jugador no tiene por que ser precisamente el
que empiece primero ya que supongamos que al elegir el numero
de cerillas y filas inicial, ya nos salga una distribución par
por columnas... con lo que el juego se vuelve un juego de azar
sobre la elección de las condiciones iniciales, que determinan
el resultado del juego, y nos podríamos ahorrar los movimientos."
En el caso del 7-5-3, es claro que el
primer jugador siempre puede llegar a un esquema par en la primera
jugada, con lo que puede ganar siempre. Le agradezco a Pere la
respuesta.
Nota: Hay que hacer una ligera modificación
a la respuesta anterior para poder aplicarla al juego tal y como
se planteó el enunciado. José H. Nieto mandó esta aclaración:
En realidad, hay dos modalidades en este
juego. La más popular es "el que retire la última cerilla pierde",
pero también se puede jugar a que "el que retire la última cerilla
gana". La solución de Antón Maynade que apareció en el BMMI
número 2 en realidad se aplica solamente a esta SEGUNDA modalidad,
ya que el jugador que logre dejar un número par de unos en cada
columna y lo siga haciendo hasta el final, evidentemente retirará
la última cerilla.
Por ejemplo si se llega a la posición
2-2 como en la partida ejemplo de Antón Maynade, si el jugador
2 quita una cerilla y el 1 restablece la paridad quitando una
de la otra fila, entonces pierde! El 1, para ganar, debe abandonar
la estrategia de restablecer paridad por columnas y eliminar la
fila con dos cerillas, para obligar al jugador 2 a quitar la última.
En general, para ganar en la primera
modalidad, hay que aplicar la estrategia descrita por Antón Maynade
pero SOLAMENTE MIENTRAS QUEDEN AL MENOS DOS FILAS CON MAS DE UNA
CERILLA CADA UNA. En el momento en que quede una sola fila con
más de una cerilla, digamos una fila con k>1 cerillas y n filas
con una cerilla cada una, hay que modificar la estrategia del
siguiente modo:
-
si n es impar, eliminamos la fila de dos cerillas
- si n es par, quitamos una cerilla de
la fila que tiene dos.
De
esta manera dejamos a nuestro oponente un número impar de filas
de una cerilla cada una, y lo obligamos a retirar la última.
Como
ejemplo supongamos que comenzamos con 1-3-5-7 (esta es la configuración
inicial más famosa, hasta apareció en el cine en la película "El
año pasado en Marienbad", de Alan Resnais). La posición está perdida
para el primer jugador, ya que al representar cada fila en binario
hay número par de unos en cada columna:
001
011
101
111
Sin embargo, si el jugador 1 es astuto
no se dará por vencido, sino que quitará por ejemplo tres cerillas
de la cuarta fila, dejando la configuración 1-3-5-4 y confiando
en que su oponente se equivoque en la siguiente jugada. En efecto,
la única jugada ganadora para 2 sería eliminar por completo la
segunda fila. Si no lo hace y por ejemplo quita una de la segunda,
dejando 1-2-5-4, el jugador 1 puede aprovechar la oportunidad
y restablecer la paridad por columnas eliminando las dos de la
segunda fila, dejando 1-0-5-4. Supongamos que ahora 2 quita 3
de la cuarta fila, dejando 1-0-5-1. Ahora 1 debe cambiar de estrategia,
quitando 4 de la tercera fila para dejar 1-0-1-1, con lo cual
gana.
