Como los minutos musicales no triunfan, vamos a por una pedantería del tito fortran. Hace unos días estaba tirado viendo la tele, con un resacón fino, y pillé empezada una serie de dibujos animados en la que por lo visto los protagonistas se enfrentaban a acertijos matemáticos y de lógica.
El problema que se trataba en el fragmento que yo vi era un concurso en un juego que posiblemente conozcáis. Se trata del juego en el que se disponen una serie de fichas (palotes, chinos, pelotillas de papel o de mocos, lo que sea) y los jugadores han de ir retirando de forma alternada un número de fichas, comprendido entre un máximo y un mínimo establecidos de antemano. El que coge la última ficha pierde. La variante más típica del juego creo que es con 20 fichas, pudiendo coger como máximo 3 y como mínimo 1.
El episodio estaba bastante bien, ya que los protagonistas encontraban la fórmula general mediante un razonamiento recursivo a partir del caso más simple en el que tenían la certeza de ganar. Resulta alentador pensar que alguien se ha preocupado de intentar inculcar una forma de pensar ordenada a los niños mediante los dibujos animados.
Recuerdo una ocasión en la que un amigo me retó a jugar, ya que él conocía la forma de ganar en el caso expuesto anteriormente (20 fichas, mínimo 1 y máximo 3). Una lástima para él no haber visto esos dibujos, que supongo que todavía no los habían creado (fue hace bastante tiempo y la serie parece actual). De nuevo lástima para él que yo me hubiese aburrido en clase de Matemática Discreta y hubiese encontrado la solución general para cualquier configuración del juego, con lo cual pude vacilarle a mi gusto propiniéndole distintas variantes y ganando siempre.
Así que aquí vamos, a ver cuál es la solución general, de un modo un poco más riguroso que en la serie de dibujos, pero partiendo más o menos de la misma base.
Para ganar en el juego, hemos de conseguir que en un movimiento nuestro, el número de fichas restantes sea mayor que cero (del contrario habremos perdido) y menor que el mínimo de fichas a retirar. De esa manera obligaremos al contrario a retirar la última ficha.
Por simplicidad, vamos a tratar primero con el caso en el que el mínimo es 1 y el máximo es M. Al comienzo del juego hay N fichas. Nuestro objetivo es dejar 1 ficha exactamente para el movimiento del contrario.
Esto se puede conseguir siempre que en el tablero queden como mucho M+1 fichas, ya que M es el máximo que podremos retirar. Si quedan R fichas, con M+1 >= R > 1 deberemos retirar un número de fichas S = R - 1. Este movimiento es legal, puesto que si restamos 1 en la desigualdad anterior, tenemos que M >= S > 0.
Por otra parte, como suponemos que nuestro rival no es lerdo, debemos intentar impedir que sea él el que se encuentre en tal disposición, por lo que en nuestro turno deberemos intentar que el número de fichas restantes R para su turno, sea mayor que M+1, ya que desde esa situación puede ganarnos retirando S fichas. De hecho, deberemos procurar, siempre que las fichas sean suficientes, dejarle en M+2 fichas, ya que en su turno, retire las que retire, se cumplirá la primera situación.
Aquí es donde entra el razonamiento recursivo. A partir de una situación sencilla en la que tenemos la certeza de ganar, hemos llegado a otra situación más compleja en la que también podemos ganar. Se puede seguir este razonamiento hasta la situación de juego inicial, pero si hay muchas fichas puede hacerse pesado. Así que vamos a recurrir a un poco de aritmética modular para simplificar el asunto.
Un hecho bastante obvio es que en dos turnos consecutivos (adversario y propio), hay un número de fichas que siempre se puede retirar, sea cual sea el movimiento del adversario. Éste número es M+m (siendo m el número mínimo de fichas que se pueden retirar). Debemos aprovechar ésto en nuestro beneficio, y lo haremos, del siguiente modo:
Como nuestro objetivo es dejar una sola ficha y tenemos la seguridad de que cada 2 turnos podemos forzar la situación para que se hayan retirado M+m fichas, hemos de conseguir que queden: [1 + k * (M+m)] fichas, siendo k un número entero mayor o igual que 0. En esa situación, habremos ganado la partida en 2*k+1 turnos.
Dicho de otra forma, hemos de asegurarnos de que cuando movamos, las fichas restantes sean congruentes con 1 bajo módulo (M+m). Esto es que el resto de dividir R entre M+m sea 1.
Conclusión: si el resto de dividir N entre (M+m) está entre 1 y m, que empieze el otro. Si es mayor que m, entonces empieza jugando y consigue que con tu movimiento R mod (M+m) esté entre 1 y m. Tras haber conseguido ésto, puedes mover siempre M+m menos lo haya movido el contrario en el turno anterior.
Espero que os haya resultado interesante...
No hay comentarios:
Publicar un comentario