jueves, 9 de julio de 2009

Juego con bolas

Fase comarcal de Alicante de la XX Olimpiada Matemática, 2009

Una caja contiene 40 bolas. Dos amigos participan en un juego extrayendo, alternativamente, bolas de la caja.

Cada uno, en su turno, puede extraer cualquier cantidad de bolas de la caja que no sea superior a la mitad de las que hay. El que no pueda extraer ninguna bola respetando las reglas, pierde el juego.

Suponiendo que los dos juegan correctamente, ¿quién ganará, el primero o el segundo en jugar?

Explica la estrategia ganadora.

Solución

2 comentarios:

Jaume Uso dijo...

Perdra el segon, per que nomes comelces, el nombre de boles es imper i vas llevant boles fins que nomes en queden dos i llavors li toca agarrar bola al segon, per que el nombre inicial era dos.(perdoneu per no ficar accents, pero s que el teclat que estic gastant es angles i no te accents)

Eynar Oxartum dijo...

Asumiendo que siempre están obligados a sacar al menos una bola (porque si no el juego no tiene sentido), sí que hay una estrategia ganadora por la que siempre gana el primer jugador (suponiendo que nadie comete errores), en cuyo comienzo el primer jugador extrae 9 bolas, dejando 31.

Sin embargo es más fácil explicarlo empezando por el final.

Ganará el jugador que consiga dejar únicamente una bola, con lo que el contrincante se ve obligado a extraer la totalidad de las bolas (una, es decir, más de la mitad) o ninguna, violando siempre una de las dos reglas fundamentales.

Sólo es posible dejar una bola si cuando es nuestro turno tenemos dos bolas. Esto sólo se puede forzar si con anterioridad hemos dejado a nuestro contrincante con tres bolas (si hubiéramos dejado cuatro, el oponente podría haber tomado sólo una, dejando tres de las que sólo podemos coger una... con lo que el oponente ganaría).

Así, nuestro problema se reduce a dejarle tres bolas a nuestro contrincante. Esto lo podemos hacer si en nuestro turno tenemos 4, 5 ó 6 bolas (si tuviéramos 7 no podríamos extraer más de tres, con lo que dejaríamos cuatro bolas y consecuentemente daríamos la victoria al oponente). Siempre que le dejemos al contrincante 7 bolas, llegaremos a nuestro turno con 4, 5 ó 6.

Ya hemos explicado suficientes pasos como para ver que se trata de una sucesión tal que A(n+1)=2*A(n)+1, siendo A(1)=1. Así,

A(1)=1
A(2)=3
A(3)=7
A(4)=15
A(5)=31
A(6)=63, etc

Siempre que le dejemos a nuestro contrincante una cantidad de bolas igual a uno de los números de esta serie, habremos ganado, ya que, independientemente de lo que él haga, nosotros podremos dejarle el elemento anterior de la serie, hasta llegar a A(1)=1.

Por ejemplo, si dejamos 15 bolas, el oponente puede:

* ... sacar una bola, dejando 14, y nosotros podremos sacar 7 bolas, dejando 7
* ... sacar dos bolas, dejando 13, y nosotros podremos sacar 6 bolas, dejando 7
* (...)
* ... sacar siete bolas, dejando 8, y nosotros podremos sacar 1 bola, dejando 7

en este caso el oponente no puede sacar ocho bolas, porque 8 > 15/2.

CONCLUSIÓN:

Para el caso particular que nos incumbe: si, habiendo 40 bolas, el primer jugador saca 9 bolas, quedarán 31 bolas para el contrincante. De este modo, el primer jugador tiene el control del juego y podrá ir forzando el paso por las distintas cantidades de la serie hasta dejar una bola y ganar.