Flipping Items Simultaneously III

Puzzle #41 in Anany and Maria Levitin's book Algorithmic Puzzles (Oxford University Press, 2011) reads:

There is a circle of n > 2 lights with a switch next to each of them. Each switch can be flipped between two positions, thereby toggling the on/off states of three lights: its own and the lights adjacent to it. Initially all the lights are off. Design an algorithm for turning all the lights on by flipping the minimum number of switches.

The applet below simplifies the mechanics of the puzzle and allows for a generalization. First, the applet makes the switches redundant. The on and off states of the lights are simulated with blue and red colors of the circles. Instead of flipping the switches, you just click on one of the circles. Second, in the puzzle, the number of the lights affected by a flip of a switch is always 3. The applet makes this number arbitrary (though greater than 1.) This makes the effect of one flip asymmteric between even and odd numbers. To smooth out the discussion, in the applet a click on a circle affects a series of circles clockwise starting with the circle that was clicked on.

So the question is,

What is the minimum number of clicks needed to change colors of all the circles?

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.

What if applet does not run?

In the applet N is the number of the circles, M is the number of the circles affected by a single click.

Discussion

What is the minimum number of clicks needed to change colors of all the circles?

What if applet does not run?

First, the answer: If M divides N, the problem is solvable - one needs N/M clicks.

More generally, let M₁ = M/gcd(M, N), N₁ = N/gcd(M, N). The puzzle is solvable if M₁ is odd in which case N₁ is the required number of clicks. For M₁ even, the puzzle is not solvable.

The state of a circle/light depends only on the number of flips this particular item has undergone - the order in which this happens is not important. This means that each of the circles may need to be clicked upon only once; and this in arbtrary order.

If K = gcd(M, N), and the solution exists as above, then the algorithm is to click on every K^th circle.

71546674