Segundo Pretorneo 2019 NJ P2

[ana19]

Alrededor de una circunferencia hay distribuidas $2n+1$ monedas todas iguales. Al comienzo, todas las monedas muestran la cara. Recorriendo la circunferencia en el sentido de las agujas del reloj se efectúan $2n+1$ cambios en el estado de las monedas (las cara pasan a cecas y viceversa): se cambia una moneda, la moneda siguiente, no se toca, se cambia la moneda que sigue, las dos monedas siguientes, no se tocan, se cambia la moneda que sigue, las siguientes tres monedas, no se tocan, se cambia la moneda que sigue, y así siguiendo hasta que finalmente se hayan salteado $2n$ monedas y la que sigue se haya cambiado. Demostrar que al finalizar este procedimiento, hay exactamente una moneda que quede en ceca.

[Gianni De Rico]

Pista muy quemadora

Spoiler: mostrar

Fijate que a partir de un punto, como se saltean tantas monedas, es lo mismo que volver para atrás. Entonces vas a volver a la misma posición cada moneda que fuiste dando vuelta salvo una.

[mszew]

Spoiler: mostrar

Siempre en estos problemas ayuda revisar los primeros casos, n=1,2,3 para ir viendo algún tipo de conclusión y luego probar con inducción y/o una formula general.

[Fran B]

Se numeran las monedas en el sentido de las agujas del relój de tal forma que la primer moneda que se da vuelta es la número 1. Además, se entiende que hablar de la moneda $K$ es lo mismo que hablar de la moneda $(2n+1)t+K$ siendo $t$ cualquier entero.
Luego, la k-ésima moneda cuyo estado fue cambiado es $\frac{k(k+1)}{2}$. Ahora queda demostrar que todos los cambios de estado, excepto uno, se pueden agrupar de a pares de tal forma que dos cambios de estado de cada par se efectúan en la misma moneda.
El cambio número $2n+1$ y $2n$ son sobre la misma moneda, ya que $\frac{(2n+1)(2n+2)}{2}=(2n+1)(n+1)=2n+1+(algo)$ y $\frac{2n(2n+1)}{2}=(2n+1)n=2n+1+(algo)$. Luego, la moneda $K$ y $2n-K$ son la misma, ya que $\frac{(2n-K)(2n+1-K)}{2}=\frac{(2n+1)(2n-K)-K(2n-K)}{2}\equiv \frac{0(2n-K)-K(-1-K)}{2}\equiv \frac{K(K+1)}{2}( mod 2n+1)$.
Pero $n=2n-n$, por lo que esa moneda será la única que quede en ceca.