Rompecabezas | Gafas al revés

Hay n vasos sobre la mesa, todos boca abajo. En un movimiento, puede entregar exactamente n – 1 de ellos. Determine todos los valores de n para los cuales todos los vasos puedan girarse en el mínimo número de movimientos.

Existen 2 casos, es decir, cuando el valor de n es impar y cuando el valor de n es par. Si el valor de n es impar, entonces no existe solución. Si el valor de n es par, el problema se puede resolver en n movimientos, que es el número mínimo de movimientos necesarios.

Si n es impar: como en un solo movimiento, podemos dar vuelta exactamente n – 1 de ellos. Si n es impar, entonces n – 1, es decir, el número de vasos volcados en un movimiento, es par. Por tanto, la paridad del número de vasos que están boca abajo siempre será impar, como lo era en la posición inicial. Por lo tanto, no se puede alcanzar la posición final en la que el número de vasos boca abajo es 0, que es par.

Si n es par: Supongamos que los vasos están numerados del 1 al n. Si n es par, el problema se puede resolver haciendo el siguiente movimiento n veces: dar la vuelta a todos los vasos excepto al i-ésimo, donde i = 1 , 2, . . . , n.
Aquí hay un ejemplo de la aplicación del algoritmo para n = 6. Denotemos los vasos invertidos con 1 y los demás con 0. Un vaso que no se voltea en el siguiente movimiento se muestra en negrita.

Si el valor de i es 1, voltee todos los vasos excepto el primero.
1 11111 –> 100000
De manera similar, si el valor de i es 2, voltee todos los vasos excepto el segundo vaso.
1 0 0000 –> 001111 De manera
similar, si el valor de i es 3, voltee todos los vasos excepto el tercero.
00 1 111 –> 111000 y así sucesivamente.
Entonces, para n = 6, esto se verá así:

1 11111 –> 1 0 0000 –> 00 1 111 –> 111 0 00 –> 0000 1 1 –> 11111 0 –> 000000

Dado que dos movimientos consecutivos cualesquiera no tendrán impacto en el estado de los vasos o cambiarán el estado de exactamente dos de ellos, ningún algoritmo puede resolver el problema en menos de n movimientos.

Referencia: Rompecabezas algorítmicos – Anany Levitin, Maria Levitin