BAMO-2014-P1

Enunciado

Alice e Bob xogan a un xogo. Ao inicio do xogo hai 20 galletas nun prato vermello e 14 galletas noutro prato azul. Os dous xugadores vanse alternando o turno do xogo, durante o cal só hai 2 movementos legais:

1. Comer duas galletas dun mesmo prato.
2. Mover una galleta do prato vermello ao azul.

Perde aquel xogador que non poida facer ningún movemento legal durante o seo turno.

Se comeza xogando Alice, ten algún dos dous xogadores una estratexia gañadora? Cal é e por que?

---

Resolución

Pista

Intenta atopar algún invariante: unha cantidade que non se modifique ao realizar un movemento legal. Tamén é útil considerar cales son os posibles estados finais, é decir, cando un xogador perde.

Solución

Denotemos o estado do xogo mediante o par $(x,y)$, onde $x$ é o número de galletas no prato vermello e $y$ o do prato azul.

É doado ver que a paridade de $x+y$ é un invariante: simplemente hay que probar que esta cantidade non varía ó aplicar un movemento legal.

Consideremos ahora os estados finais do xogo. En un primeiro lugar podemos considerar só os estados onde non podemos realizar o movemento legal $(1)$, e estes estados son $(1,1),(1,0),(0,1),(0,0)$. É doado ver que no caso de enfrentarnos ós estados $(1,0),(1,1)$ poderíamos seguir xogando facendo o movemento legal $(2)$, polo que non son estados finais.

Por outro lado, o estado inicial é $(20,14)$ e $20+14=34$ é par, polo que todo estado válido ten que cumprir que o número de galletas totales sexa par (debido ó invariante obtido anteriormente). Debido a esto descubrimos que o estado $(0,1)$ é inalcanzable, polo que o único estado final é $(0,0)$. Esto implica que para terminar o xogo é necesario comer todas as galletas, polo que deben realizarse $\frac{20+14}{2}=17$ movementos $(1)$.

Ademáis, durante o xogo tamén poden realizarse un certo número $n$ de movementos $(2)$, pero é doado ver que $n$ é par: ao inicio o número de galletas en cada prato é par, e o movemento $(2)$ cambia a paridade de estes números. Agora ben, como as galletas cómense de dous en dous, é necesario que $n$ sea par, porque senón o número de galletas dos pratos serían impares e non poderíamos chegar o estado $(0,0)$, que é o único estado final.

Por ende, temos que toda partida a este xogo tendrá $17+n$ movementos con $n$ par, polo que toda partida finalizará cun número impar de movementos legais (xa que $17+n$ é impar). Como vánse alternando os turnos, esto implica que ó último turno legal sempre o tendra o xogador que empeza, e dicir Alice, polo que Bob sempre perderá. Concluimos que Alice sempre gañará.

---

Dúbidas & Comentarios

Nesta sección pódesnos deixar as túas dúbidas e comentarios a cerca do problema anterior. Non teñas teima en preguntar, estamos aí para botar un man!