Algoritmia básica (AB)
El reto de diseñar algoritmos eficientes para resolver problemas puede resultar apasionante

sguenos en twitter
La solución de Alice
5 septiembre 2012 por Javier Campos en Problemas

Veamos qué se le ocurrió a Alice para ganar a Bob siempre que fuera posible (en el juego que quedó pendiente en julio).

Al principio hemos considerado un juego con dos montones de 10 piedras cada uno, denominaremos ese juego como 10+10 y a un montón le llamaremos A y al otro B. De esta manera, n+m es un juego en el que el montón A tiene n piedras y el montón B tiene m piedras.

Alice rellenó poco a poco, y empezando por los valores bajos de n y m, una tabla como la que se incluye arriba, en la que las filas corresponden al montón A y las columnas al montón B. Cada casilla de la tabla contiene un símbolo que puede ser una flecha o un asterisco. La flecha indica la casilla a la que Alice debe moverse para mantener intactas sus opciones de victoria. Por ejemplo, la flecha ← de la casilla (2,3) indica que tiene que retirar una piedra del montón B. Un asterisco en (i,j) quiere decir que, si Bob también sabe jugar así de bien, no hay opción de ganarle en el juego i+j

Como Bob no podía soportar más esta situación, optó finalmente por matricularse en Algoritmia Básica.

Fuente: An Introduction to Bioinformatics Algorithms, Neil C. Jones y Pavel A. Pevzner. The MIT Press, 2004.

Comentarios