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

sguenos en twitter
Bob y Alice se entretienen jugando
13 julio 2012 por Javier Campos en Problemas

Bob y Alice se aburren un sábado por la tarde. Como sólo disponen de 20 piedras para entretenerse, deciden agrupar las piedras en dos montones de 10 y jugar al siguiente juego:

  1. En cada turno, un jugador puede coger una piedra de un montón o una piedra de ambos montones.
  2. Una vez cogidas, las piedras son retiradas del juego.
  3. Gana el jugador que coge la última piedra.
  4. Empieza Alice.

En un principio, no está claro cuál es la estrategia ganadora, o incluso si existe una. ¿Tiene el primer jugador o el segundo siempre ventaja? Bob intenta analizar el juego y rápidamente se da cuenta de que existen demasiadas variantes en un juego con 10 piedras en cada montón. Así que intenta diseñar una estrategia para un juego con 2 piedras por montón, de esta manera obtiene la siguiente “receta ganadora”:

Si Alice coge una piedra de ambos montones, yo cogeré las piedras sobrantes (una de cada montón) y ganaré. Si Alice coge sólo una piedra, yo cogeré la otra piedra del mismo montón. Así la única opción de Alice será coger una piedra del otro montón, yo podré coger la que queda y ganaré.

Entusiasmado con esta estrategia, Bob, generaliza de manera directa su estrategia para un juego de n piedras por montón, y haciendo un acto de fe, asume que el segundo jugador siempre puede ganar si n >= 2. Sin embargo, no siempre gana.

Por su parte Alice, que ha cursado Algoritmia Básica, diseña una estrategia general y fácil de aplicar que le asegura la victoria para ciertos valores de n.

¿Sabrías decir cuáles son esos valores? ¿En qué consiste la estrategia?

Fuente: Se publicará más adelante…

Volvemos en septiembre, os deseamos buen verano.


Bob y Alice


Comentarios