Rompecabezas | El círculo de luces

Hay un círculo de N > 2 luces con un interruptor al lado de cada una de ellas. Cada interruptor se puede girar entre dos posiciones, alternando así los estados de encendido/apagado de tres luces: la suya propia y las dos luces adyacentes . Inicialmente, todas las luces están apagadas. Diseñe un algoritmo para encender todas las luces accionando el número mínimo de interruptores.

Solución:
dado que todas las luces están apagadas inicialmente, es obvio que el estado final de las luces depende solo de la paridad (par o impar) de la cantidad de veces que se acciona cada interruptor y no depende del orden en que se activan los interruptores. son manipulados. Para encender una luz, podemos accionar su interruptor y dejar los interruptores adyacentes apagados, o accionar los tres interruptores, para un grupo de tres luces. Suponiendo que las luces están numeradas del 1 al N en el sentido de las agujas del reloj , tenemos dos casos.

1. N es divisible en 3: En este caso, ^accionamos el interruptor de la 1ª bombilla, que enciende las bombillas 1, 2 y N. Luego accionamos el interruptor de la 4ª ^bombilla , que enciende la bombilla 3 , 4 y 5 . De esta manera, accionamos el interruptor de cada bombilla 3K + 1 hasta que accionamos el interruptor de la bombilla N – 2 , que encenderá las últimas 3 bombillas. Esto da como resultado un total de N/3 cambios de interruptor.
   
2. N no es divisible por 3: En este caso, supongamos que seguimos el mismo procedimiento anterior. Esto solo encenderá las bombillas en múltiplos de 3 . Entonces, al final, habrá una o dos bombillas , que estarán apagadas. Al accionar el interruptor de una de estas bombillas, apagamos al menos una bombilla. Esta bombilla, digamos X , que ahora se apagó debido al giro anterior, se encendió un número par de veces, para encenderla, se debe girar el interruptor de X o uno de sus focos adyacentes que no se encendió. . De esta forma, tenemos que accionar el interruptor de cada una de las bombillas cuyo interruptor no ha sido accionado. Esto da como resultado un total de N cambios de interruptor.