# 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?

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.

|Up| |Contact| |Front page| |Contents| |Algebra| |Eye opener|

Copyright © 1996-2018 Alexander Bogomolny

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_{1} = M/gcd(M, N), N_{1} = N/gcd(M, N). The puzzle is solvable if M_{1} is odd in which case N_{1} is the required number of clicks. For M_{1} 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.

|Activities| |Contact| |Front page| |Contents| |Algebra| |Eye opener|

Copyright © 1996-2018 Alexander Bogomolny