{"id":2178,"date":"2021-09-04T18:59:48","date_gmt":"2021-09-04T18:59:48","guid":{"rendered":"https:\/\/blogs.ua.es\/dimates\/?p=2178"},"modified":"2021-09-04T18:59:48","modified_gmt":"2021-09-04T18:59:48","slug":"solucion-a-arrinconadas","status":"publish","type":"post","link":"https:\/\/blogs.ua.es\/dimates\/2021\/09\/04\/solucion-a-arrinconadas\/","title":{"rendered":"Soluci\u00f3n a arrinconadas"},"content":{"rendered":"
Problema 5 de la fase catalana de la 57 Olimpiada Matem\u00e1tica Espa\u00f1ola (2020\/21)\r\nSe dirige a una edad de: 16-17 a\u00f1os<\/pre>\n
Ana y Bernat juegan un juego sobre un tablero ajedrezado de dimensiones 2020×2020.<\/p>\n
Decimos que una colecci\u00f3n de piezas puestas en ese tablero est\u00e1 arrinconada (en la esquina inferior izquierda) si no hay ninguna casilla vac\u00eda de forma que la casilla inmediatamente superior o inmediatamente a la derecha de ella contenga una pieza, como se muestra en la figura.<\/p>\n
Inicialmente, hay 2020 piezas colocadas en una posici\u00f3n arrinconada.<\/p>\n
En turnos alternos, comenzando por Ana, cada jugador retira dos piezas de casillas adyacentes (con un lado en com\u00fan), con la condici\u00f3n de que la configuraci\u00f3n restante siga siendo arrinconada.<\/p>\n
Pierde el jugador que no puede hacer un movimiento.<\/p>\n
Determina cu\u00e1l de los dos jugadores ganar\u00e1 en funci\u00f3n de la posici\u00f3n inicial de las 2020 piezas, suponiendo que ambos jueguen de forma \u00f3ptima.
\n\"\"
\nSoluci\u00f3n:
\n
\nEs un problema mucho m\u00e1s complejo de lo que parece.<\/p>\n
Para empezar, tratemos casos m\u00e1s sencillos. Si probamos la combinaci\u00f3n con s\u00f3lo 4 fichas, tenemos que, empecemos en la combinaci\u00f3n que empecemos, gana Bernat, ya que siempre que Ana pueda jugar, le deja 2 a Bernat en una posici\u00f3n arrinconada, es decir, que una de ellas debe estar en la esquina y la otra en una de las casillas blancas, as\u00ed que perfectamente puede jugar su turno y Ana se queda sin poder hacer nada.<\/p>\n
La situaci\u00f3n para 6 fichas es m\u00e1s variada. Si la posici\u00f3n inicial es una en especial (la que forma un tri\u00e1ngulo, la de la esquina, las dos blancas en contacto con ella, y las tres negras en contacto con ellas) pierde Ana, ya que no puede hacer su movimiento sin que dejen de estar arrinconadas. Pensemos que en ese caso, lo que sucede es que cualquier jugada de Ana debe incluir una de las fichas blancas, y una negra, y es evidente que en cualquier caso deja a otra negra con un cuadro vac\u00edo bajo o a la izquierda, luego no es arrinconada.<\/p>\n
Sin embargo, en cualquier otra circunstancia, Ana puede jugar, y le pasa una situaci\u00f3n perdedora a Bermat. Luego pierde Bernat. Vamos a estudiar una de estas situaciones.
\n\"\"
\nVemos que Ana tiene dos recursos: jugar con la blanca m\u00e1s a la derecha y llevarse una negra de las que le acompa\u00f1an, de forma que queda una de las posiciones de 4 que ya hemos analizado.<\/p>\n
Despu\u00e9s de este experimento, sacamos varias conclusiones. Existen jugadas en las que, aunque hay fichas, uno no puede hacer su jugada, y parece ser que en ese caso las fichas forman un tri\u00e1ngulo, la persona a la que le toca jugar no puede jugar. El n\u00famero de fichas debe ser par, as\u00ed que el tri\u00e1ngulo ser\u00eda de 3 fichas de lado, o de 4, o de 6, o de 7, o de 8. En esos casos, si a lo largo de las partidas se llega a esas construcciones, la persona no va a poder jugar y perder\u00e1.<\/p>\n
La clave es entender de qu\u00e9 forma se puede predecir, cuando tenemos una gran cantidad de fichas (2020), si estamos en una de las situaciones en las que el juego se para antes de acabar, o llega al final, en cuyo caso la que tendr\u00eda una situaci\u00f3n desfavorable es Ana, ya que coincidir\u00eda que despu\u00e9s de 1010 pares de movimientos, le toca jugar y no hay piezas.<\/p>\n
Por otra parte, si llegamos a una situaci\u00f3n con 6 fichas dispuestas de la forma que hemos visto anteriormente (en 3 diagonales) o 10 fichas (4 diagonales) le tocar\u00eda jugar a Bernat (quedan 3 o 5 movimientos con fichas, pero no se puede seguir).<\/p>\n
Sin embargo, si la situaci\u00f3n es con 7 diagonales (28 fichas) u 8 diagonales (36 fichas), quedan 14 o 18 movimientos, de forma que a quien le tocar\u00eda jugar es a Ana, que ser\u00eda la que perder\u00eda. \u00bfC\u00f3mo podemos identificar esas situaciones?<\/p>\n
Si atendemos a que en cada movimiento se retiran una ficha en una casilla blanca y una ficha en una casilla negra, nos daremos cuenta de que la diferencia entre ambos tipos de fichas se mantiene constante, por lo que si esa diferencia es una caracter\u00edstica del n\u00famero de diagonales que quedan al final, resulta que no tendremos m\u00e1s remedio que llegar a esa situaci\u00f3n desde una determinada situaci\u00f3n de partida.<\/p>\n
Observamos que el caso de 3 diagonales, la diferencia entre blancas y negras ocupadas es 2 a favor de las negras, mientras que para 4 diagonales es 2 a favor de las blancas. Para el caso en que lleguemos a la final de la partida, deber\u00eda de haber la misma cantidad de negras y blancas. Luego la disposici\u00f3n inicial parece que decide hasta d\u00f3nde llegaremos.<\/p>\n
Otra pista es que en el caso de 7 diagonales, el n\u00famero de fichas negras ser\u00eda 1 + 3 + 5 + 7 = 16, y el de blancas 2 + 4 + 6 = 12, luego hay una diferencia de 4 fichas negras. Y en el caso de 8 diagonales, habr\u00eda una diferencia de 4 hacia las fichas blancas.<\/p>\n
S\u00f3lo nos queda demostrar que esto es algo general, y que una posici\u00f3n en la que no haya un n\u00famero entero de diagonales siempre se puede seguir jugando.<\/p>\n
En efecto, siempre se puede seguir jugando si no tenemos un n\u00famero entero de diagonales. Al estar las fichas arrinconadas, las l\u00edneas est\u00e1n totalmente rellenas de fichas hasta la \u00faltima ficha. Si no est\u00e1n completas las diagonales, o bien hay una fila en la que hay al menos dos fichas m\u00e1s que en la anterior, en cuyo caso se pueden quitar las dos \u00faltimas, o bien hay dos filas iguales, en cuyo caso, la primera vez que ocurra se pueden quitar las dos \u00faltimas fichas de estas dos filas.<\/p>\n
Para que exista la posibilidad de que se llegue a una situaci\u00f3n en la que hay n diagonales enteras ocupadas, con n impar, el n\u00famero de fichas negras ser\u00eda (1 + n)\u00b7(1 + n)\/4 = (n\u00b2 + 2n + 1)\/4 y el n\u00famero de fichas blancas ser\u00eda de (2 + n \u2013 1)\u00b7(n \u2013 1)\/4 = (n\u00b2 \u2013 1)\/4, usando progresiones aritm\u00e9ticas para sumar las dos progresiones, y la diferencia ser\u00eda exactamente de (2n+2)\/4 = (n + 1)\/2 fichas (a favor de las negras). Eso s\u00f3lo puede suceder, evidentemente, si n es de la forma 4k \u2013 1, ya que no puede haber una diferencia impar entre blancas y negras.<\/p>\n
Por otra parte, si n es par y queremos tener n diagonales enteras, entonces el n\u00famero de fichas negras es de (1 + n \u2013 1)\u00b7n\/4 = n\u00b2\/4, y el n\u00famero de fichas blancas es de (2 + n)\u00b7n\/4 = (n\u00b2 + 2n)\/4, de forma que la diferencia esta vez ser\u00e1 en favor de las blancas, y de 2n\/4 = n\/2, cosa que s\u00f3lo podr\u00e1 ocurrir si n es m\u00faltiplo de 4, por similares razones.<\/p>\n
De esta forma, seg\u00fan que las fichas arrinconadas en el tablero tengan una u otra diferencia en favor de las blancas o las negras, conociendo esa diferencia podremos deducir a cu\u00e1ntas diagonales enteras vamos a acabar, independientemente de c\u00f3mo juguemos. Porque si pudiesen quedar al final menos diagonales, la diferencia ser\u00eda menor que la que es, y eso es imposible.<\/p>\n
Por ejemplo, si hay m\u00e1s blancas que negras, pongamos 8 blancas m\u00e1s que negras, llegaremos a un n\u00famero par de diagonales enteras, exactamente 16, y no podremos continuar, luego ganar\u00eda Ana, ya que le tocar\u00eda jugar a Bernat cuando lleg\u00e1semos a esa situaci\u00f3n.<\/p>\n
Una vez decidido esto, para saber qui\u00e9n gana, debemos ver la paridad de las jugadas que quedan, ya que el n\u00famero total de diagonales (la n), determina que al final quedar\u00e1n (1 + n)\u00b7n\/2 = (n\u00b2 + n)\/2 fichas, y el n\u00famero (n\u00b2 + n)\/4 ser\u00e1 el n\u00famero de jugadas. Si este n\u00famero es par, ganar\u00e1 Bernat (como en el caso de que n = 7 o n = 8) mientras que si es impar, ganar\u00e1 Ana (como en el caso en que n = 3 o n = 4).<\/p>\n
As\u00ed que el invariante que determina la partida, en realidad, no es la posici\u00f3n en s\u00ed misma, si no la diferencia entre n\u00famero de casillas blancas y negras ocupadas.<\/p>\n
Esta diferencia debe ser par, ya que inicialmente hay 2020 fichas, y si la cantidad de fichas en posici\u00f3n blanca es par, tambi\u00e9n lo es la cantidad en posici\u00f3n negra, y viceversa.<\/p>\n
Si hay 2k blancas m\u00e1s que negras, quedar\u00e1n al final 2k diagonales, y (4k\u00b2 + 2k)\/2 = 2k\u00b2 +k fichas, as\u00ed que el valor de k par nos dir\u00e1 que gana Ana y el valor de k impar nos dice que gana Bernat. Si hay 2k negras m\u00e1s que blancas, en ese caso, (n + 1)\/2 = 2k, luego n = 4k \u2013 1, y quedar\u00e1n al final ((4k \u2013 1)\u00b2 + (4k \u2013 1))\/4 jugadas, y eso es (16k\u00b2 \u2013 4k)\/4 = 4k\u00b2 \u2013 k, cuya paridad en realidad depende de nuevo de k, es decir, que si k es par sigue ganando Ana y si k es impar, Bernat.<\/p>\n","protected":false},"excerpt":{"rendered":"
Problema 5 de la fase catalana de la 57 Olimpiada Matem\u00e1tica Espa\u00f1ola (2020\/21) Se dirige a una edad de: 16-17 a\u00f1os Ana y Bernat juegan un juego sobre un tablero ajedrezado de dimensiones 2020×2020. Decimos que una colecci\u00f3n de piezas puestas en ese tablero est\u00e1 arrinconada (en la esquina inferior izquierda) si no hay ninguna […]<\/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-2178","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\/2178","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=2178"}],"version-history":[{"count":1,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/2178\/revisions"}],"predecessor-version":[{"id":2180,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/posts\/2178\/revisions\/2180"}],"wp:attachment":[{"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/media?parent=2178"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/categories?post=2178"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.ua.es\/dimates\/wp-json\/wp\/v2\/tags?post=2178"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}