{"id":1591,"date":"2020-03-28T19:25:15","date_gmt":"2020-03-28T19:25:15","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=1591"},"modified":"2020-03-28T19:25:15","modified_gmt":"2020-03-28T19:25:15","slug":"solucion-a-juego-de-piedras","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2020\/03\/28\/solucion-a-juego-de-piedras\/","title":{"rendered":"Soluci\u00f3n a juego de piedras"},"content":{"rendered":"
Problema 7 de la Fase Local de la LVI OME 2020\r\nSe dirige a una edad de: 16-17 a\u00f1os<\/pre>\n
Ana y Bernardo juegan al siguiente juego.<\/p>\n
Se empieza con una bolsa que contienen n >= 1 piedras.<\/p>\n
En turnos sucesivos, y empezando por Ana, cada jugador puede hacer los siguientes movimientos:<\/p>\n
Si el n\u00famero de piedras de la bolsa es par, el jugador puede coger una sola piedra o la mitad de las piedras.<\/p>\n
Si el n\u00famero de piedras de la bolsa es impar, tiene que coger una \u00fanica piedra.<\/p>\n
El objetivo del juego es coger la \u00faltima piedra.<\/p>\n
Determinar para qu\u00e9 valores de n tiene Ana una estrategia ganadora.
\n\"\"
\nSoluci\u00f3n:
\n
\nEn este tipo de problemas, hay que estudiar una estrategia hasta tener una conjetura v\u00e1lida, y siempre se empieza por el final.<\/p>\n
Si al comienzo hay una \u00fanica piedra, Ana gana seguro (es una cantidad por tanto ganadora).<\/p>\n
Si hay 2, Ana se ve obligada a tomar una y pierde. 2 es por tanto un n\u00famero perdedor.<\/p>\n
Si hay 3, Ana gana autom\u00e1ticamente (3 es ganador).<\/p>\n
Si hay 4, Ana puede quedarse con 2 y pasarle un n\u00famero perdedor a Bernardo. 4 es, por tanto, un n\u00famero ganador tambi\u00e9n.<\/p>\n
Si hay 5, estamos ante un n\u00famero perdedor.<\/p>\n
Si hay 6, es un n\u00famero ganador si quitamos uno.<\/p>\n
Si hay 7, es perdedor.<\/p>\n
Si hay 8, es ganador quitando uno.<\/p>\n
Creo que ya tenemos suficiente para hacer una conjetura. Todo n\u00famero impar mayor que 3 es perdedor, y todo n\u00famero par mayor que 2 es ganador. El 1 es ganador, 2 es perdedor y 3 es ganador.<\/p>\n
Demostremos la veracidad de la conjetura por inducci\u00f3n.<\/p>\n
Hemos visto que es cierto si n es menor que 7, supongamos que es cierto hasta un determinado n\u00famero n (es decir, todos los menores que n, si son pares, te permiten ganar, y si son impares, te hacen perder).<\/p>\n
Supongamos que n es impar. Puesto que tenemos que sacar una \u00fanica piedra, devolveremos un valor par a nuestro adversario, que le permitir\u00e1 ganar.<\/p>\n
Si n es par, estudiaremos si n\/2 es impar o no. Si es impar, quitaremos la mitad de piedras, y si no lo es, s\u00f3lo quitaremos una. En cualquier caso, dejaremos un n\u00famero impar mayor que 3 (recuerda que hemos estudiado hasta el 6), por lo que ser\u00e1 un n\u00famero perdedor y habremos ganado.<\/p>\n
Esto demuestra que si el n\u00famero de partida es par mayor que 2, o impar menor que 5, ganamos. En caso contrario, no. Y la estrategia es la descrita.<\/p>\n
Un ejemplo con el 200, pasar\u00edamos a 199, 198, 99, 98, 49, 48, 47, 46, 23, 22, 11, a 10, a 5, a 4, a 2 a 1 y ganamos.<\/p>\n","protected":false},"excerpt":{"rendered":"
Problema 7 de la Fase Local de la LVI OME 2020 Se dirige a una edad de: 16-17 a\u00f1os Ana y Bernardo juegan al siguiente juego. Se empieza con una bolsa que contienen n >= 1 piedras. En turnos sucesivos, y empezando por Ana, cada jugador puede hacer los siguientes movimientos: Si el n\u00famero de […]<\/p>\n","protected":false},"author":4267,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2242021,1738,2849,3303],"tags":[],"class_list":["post-1591","post","type-post","status-publish","format-standard","hentry","category-olimpiada-matematica-espanola","category-olimpiadas","category-problemas","category-soluciones"],"_links":{"self":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/1591","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/users\/4267"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/comments?post=1591"}],"version-history":[{"count":1,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/1591\/revisions"}],"predecessor-version":[{"id":1592,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/1591\/revisions\/1592"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=1591"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=1591"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=1591"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}