jueves, 23 de julio de 2009

Juego con bolas

Enunciado

Como dice Eynar en los comentarios, la clave para diseñar una estrategia en los juegos por turnos, es imaginarse una versión reducida del juego, o el final del juego, e ir reconstruyendo hasta el principio, si no hay una alternativa mejor.

¿Cuál es el mínimo número de bolas que puede haber en la caja? Observa que cada participante debe sacar una bola como mínimo, y el máximo de bolas que puede sacar es la mitad. Por lo que en el caso en que sólo queda una bola en la caja, no se pueden cumplir las dos condiciones a la vez. A partir de ahí, el que consiga estar en posición de tener dos bolas en la caja gana, pues puede sacar una, y deja al rival una posición perdedora.

Tres bolas es una posición perdedora, ya que sólo podemos sacar una bola, y dejamos una posición segura a nuestro rival.

Si tenemos 4, 5 o 6 bolas en la caja, podemos sacar 1, 2 o 3, respectivamente, dejando al rival una posición perdedora.

Tener 7 bolas es una posición perdedora, ya que no tenemos más remedio que sacar 1, 2 o 3 bolas, dejando 6, 5 o 4, respectivamente.

Por encima de 7, hasta 15, cualquier posición es ganadora, ya que dejaríamos 7 bolas al rival.

De forma similar, 15, 31, 63, 127, .... son posiciones perdedoras, ya que nos permiten ir pasando de una a otra, dejando al rival una nueva posición perdedora, hasta hacerle perder cuando llega a tener una única bola. Observa que cada posición perdedora es el doble de la anterior, más una bola.

En el caso que nos ocupa, puesto que empezamos con 40 bolas, suponiendo que empecemos nosotros, para tener asegurada la victoria debemos quitar 9, dejando 31 bolas a nuestro rival. Haga lo que haga, deja un total entre 16 y 30, al que nosotros deberemos sacar entre 1 y 15 para dejarle 15. De nuevo, él jugará para dejarnos entre 8 y 14, y nosotros dejaremos 7 sacando entre 1 y 7. El siguiente turno de nuestro rival nos dejará entre 4 y 6, permitiendo que nosotros le dejemos 3 quitando 1, 2 o 3. Ya no hay más posibilidades, ya que sólo podrá sacar una bola, y nosotros también tendremos que sacar una, lo que llevará a la derrota del contrario.