Solitario en ronda

Sobre la mesa hay varias monedas formando una ronda. Todas muestran la cara. El objetivo es que queden dadas vuelta mediante el siguiente procedimiento.

Damos vuelta una cualquiera. Nos movemos en el sentido de las agujas del reloj un lugar y damos vuelta la moneda que esté allí. Luego nos movemos dos lugares (siempre en el mismo sentido) y damos vuelta la moneda que encontramos. Luego nos movemos tres lugares… Si nos encontramos con una moneda que ya está dada vuelta, entonces perdimos.

Es fácil comprobar que cuando la ronda tiene siete monedas, perdemos. Pero cuando la ronda tiene ocho monedas, ganamos.

¿Cuántas monedas debe tener una ronda para que podamos ganar? ¿Por qué?

—Ivan Skvarca

7 comentarios Hacer un comentario

  • 1. Santiago  |  Jan 20 2012, 2:50 am

    ¿Hay que hacer obligados los primeros tres pasos? porque si no, con una y dos monedas ganas trivial. Tres pierdes, cuatro ganas… ¿potencias de dos? La explicación formal no me sale, pero me da que es igual que como se construyen los binarios, restando 1. A ojo.

  • 2. Marcos  |  Jan 20 2012, 12:25 pm

    En http://oeis.org/A105198 explican:

    Si N es una potencia de 2 entonces n(n+1)/2 mod N es un patrón repetitivo de longitud 2N. Además, los primeros N restos forman una permutación {0,1,…,N-1}. Los subsiguientes N restos son los mismos pero en sentido inverso.
    Al ir sumando 1, 2, 3, etc a las movidas, estamos generando los números de la forma n(n+1)/2, y por ende recorriendo esos mismos restos, que si N es potencia de dos serán todos distintos.

    Lo que haría falta para completar la explicación sería demostrar que si N no es potencia de 2, entonces los restos se repetirán…

  • 3. Homero  |  Jan 20 2012, 12:40 pm

    Se ve muy bueno el problema…

    Sin tenerlo completamente resuelto, creo que tengo un par de ideas con las que se podría resolver.

    Lo primero, observar que si uno resuelve un círculo, y después parte desde la última moneda hacia el lado contrario, uno visita las monedas en orden inverso, es decir, hay una especie de simetría en el recorrido. Esto pasa porque moverse X lugares a la derecha es lo mismo que moverse N – X a la izquierda (N es el total de monedas).

    Una segunda idea es que creo que se puede mostrar que si el círculo de tamaño N tiene solución, entonces el de 2N también, porque ya sabemos que podemos dar vuelta las primeras N monedas, y las siguientes son un reflejo de la primera mitad, por lo que explicaba antes.

    Esto es una idea vaga de cómo podríamos demostrar por inducción que con N potencia de 2 siempre hay solución, pero deja pendiente ver si existen soluciones fuera de las potencias de 2…

    Saludos!!

  • 4. Santiago  |  Jan 20 2012, 9:12 pm

    Expando un poco lo de los binarios, que me quedó “críptico”: los enteros anteriores a “cada” potencia de dos en binarios se escriben con puros unos (salvo el cero).
    1 -1, 3 -11, 7 -111 etc. La analogía sería pensar las monedas volteadas como unos, y las que se quedan sin voltear como ceros. No es correcto, porque el juego de siete monedas tiene siete lugares, no tres, pero vale la pena tenerlo en mente.

    Volviendo al tema: es claro que si hay solución para N monedas, el número de turnos tiene que ser exactamente igual al número de monedas. Es decir, que el número de movimientos sobre el círculo es igual a la suma de los enteros menores a N (el primero es cero), (0+1+2…+N-1); al mismo tiempo la suma de las monedas volteadas (todas, y pensando también en la “moneda cero”) debe ser exactamente el mismo.

    Cada turno x se voltea la moneda “(0+1+… +x) mod N”

    de modo que si todo ha ido bien, después del turno están volteadas 0 mod N, 1 mod N, 3 mod N … y (0+1+… +x) mod N

    Es decir, si hay solución, las monedas volteadas son
    {0 mod N, (0+1) mod N, (0+1+2) mod N, …, (0+1+2 …+N-1) mod N}

    y, por lo de arriba,
    [0 mod N + (0+1) mod N + (0+1+2) mod N + ... + (0+1+2 ...+N-1) mod N] = 0+1+2…+N-1

    Es decir, a grandes rasgos, que el número de turnos es igual al número de monedas.

    y como decía mi profesor de cálculo, es trivial demostrar que eso sólo sucede si N es potencia de 2

    “Trivial” siempre significó que yo no lo podía hacer, pero quizá por ahí sale. Si no, hay que ver que para N potencia de 2 cada “(0+1+… +x) mod N” es distinto de los anteriores, y si N no es potencia de 2 siempre hay uno que se repite, pero creo que es más trabajoso y lo otro alguien que sepa bien de aritmética lo podrá demostrar.

    Saludos!

  • 5. Gustavo Piñeiro  |  Jan 22 2012, 11:25 am

    Lo que voy a decir no resuelve el problema, pero creo que puede servir de ayuda:

    Afirmo que si n es impar entonces existen dos números triangulares diferentes que son congruentes entre sí módulo n. (De hecho, n es la diferencia entre dos números triangulares.)

    Una demostración informal de esta afirmación sería así: tomemos, por ejemplo, n = 11. Todo impar es suma de dos números consecutivos, en nuestro ejemplo: 11 = 5 + 6.

    Llamemos Tk al k-ésimo número triangular. T0 = 0, T1=1, T2=3, etc.
    Luego: Tk – T(k-1) = k.

    Entonces: T6 – T4 = (T6 – T5) + (T5 – T4) = 6 + 5 = 11

    Por lo tanto T6 y T4 son congruentes entre sí módulo 11. Lo mismo puede hacerse con cualquier otro número impar, si n = k + k + 1 entonces n = T(k+1) – T(k-1).

    Una demostración más formal podría hacerse así: si n = 2k + 3 entonces es inmediato ver que
    ((k+2)^2 – (k+2))/2 – (k^2 + k)/2 = n

    Yendo al problema en sí, si N no es potencia de 2 entonces N es impar , o bien el producto de una potencia de 2 por un número impar mayor que 1.

    Si N es impar, ya sabemos que hay dos triangulares congruentes entre sí módulo N. Falta resolver el otro caso.

  • 6. Gustavo Piñeiro  |  Jan 22 2012, 11:27 am

    Fe de erratas:
    Donde dice
    ((k+2)^2 – (k+2))/2 – (k^2 + k)/2 = n

    Debió decir:
    ((k+2)^2 + (k+2))/2 – (k^2 + k)/2 = n

  • 7. Enrique Garcia  |  Jan 24 2012, 9:59 pm

    Hola Ivan:
    Curiosamente en el problema de Josefo, cuando se elimina sucesivamente una persona del círculo de cada dos, ocurre que si el número de personas es una potencia de dos, el sobreviviente siempre es el que se ubica en el primer lugar. ¿Tendrá esto alguna oscura relación con el problema de las monedas?
    Soy un profesor de matemáticas de Perú que encuentra tus problemas muy interesantes. Tengo una biblioteca bastante amplia de juegos de ingenio y matemáticas recreativas, pero hasta ahora no he podido conseguir tu libro “120 acertijos para hacerse el bocho”. ¿Podrías ayudarme a conseguirlo?
    Mil gracias

Hacer un comentario

(no se publica)

Es posible que su comentario deba ser aprobado antes de la publicación. Sea paciente. Si lo desea puede usar un poco de HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> , pero si todo esto no tiene sentido actúe normalmente. Evite escribir todo con mayúsculas. Sea amable.


Esta es una anotación de juegosdeingenio.org, un weblog dedicado a los juegos de ingenio, los acertijos y todo lo demás. Debajo de algunas notaciones aparecen comentarios de otros lectores; usted puede dejar el suyo o bien escribirle directamente al responsable. Las anotaciones más recientes se pueden ver en la página inicial.