Enunciado
Dous xogadores Alice e Bob tórnanse no seguinte xogo: Hai un montón de 2003 pedras. Na primeira quenda, Alice escolle un divisor de 2003 e retira este número de pedras do montón. A continuación, Bob escolle un divisor do número de pedras restantes, e retira ese número de pedras do novo montón, e así sucesivamente. O xogador que teña que retirar a última pedra perde. Demostra que un dos dous xogadores ten unha estratexia gañadora e descríbea.
Resolución
Solución
Este é un xogo finito (sen posibilidade de empate), polo que eventualmente un dos dous xogadores gaña e o outro perde. Nótese que a única forma de que un xogador perda é que na súa quenda se atope cun montón conformado por unha única pedra: se hai pedras, entón o xogador pode sempre quitar unha pedra e polo tanto o xogo continuaría. Polo tanto, unha estratexia gañadora pode basearse en sempre ter un montón par de pedras. Desta forma, o xogador nunca se atoparía cunha única pedra (xa que unha é impar), polo que nunca perdería. Como o xogo finito, isto implica que eventualmente gañaría. Isto é xusto o que ocorre na estratexia anterior. Na primeira quenda de Bob hai 2002 pedras, un número par. Se Bob retira un número impar é impar, polo que Alice está obrigada a quitar un número impar de pedras. Impar menos impar é par, polo que Bob atoparase de novo cun número par, tal como queriamos. Para que Bob poda usar esta estratexia, ten que sempre poder quitar un número impar de pedras. Agora ben, 1 é sempre divisor, polo que sempre pode quitar unha pedra.
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 unha man!