Switch

Relevant wiki: Information Compression

General solution:

Let us have $n$ light bulbs labeled $a_1, a_2, \cdots, a_n$ and $n$ switches labeled $b_1, b_2, \cdots, b_n$ .

$$

If $n \leq 3$ clearly the minimum number of flicks is $1$ since any flick causes every light bulb to turn on.

Now, if $n > 3$ is divisible by $3$ clearly the minimum number of flicks needed is $\frac{n}{3}$ because flicking every third switch turns every light bulb on.

$$

However, if $n > 3$ is not divisible by $3$ the minimum number of flicks needed is $n$ .

Proof:

If we flick a switch, for instance $b_i$ , lamps $a_{i-1}, a_{i} \text{ and } a_{i+1}$ turn on.

Now if we flick $b_{i+1}$ by induction we must also flick $b_{i+2}$ and hence every switch must be flicked resulting the minimum number of flicks to be $n$ . Also, by symmetry, flicking $b_{i-1}$ gives the same result.

If we flick $b_{i+2}$ we must also flick $b_{i+1}$ because lamp $a_{i+1}$ is on and flicking any switch again makes no sense, since we already have flicked it. This gives the same result.

Now we are forced to flick $b_{i+3}$ since it is the only possible way to try to turn lamp $a_{i+2}$ on without flicking every switch.

$$

We continue like this, flicking every third switch, but this results in us flicking every switch because $n$ is not divisible by $3$ .

Thus, the minimum number of flicks in this case is $n$ . $\square$

Answer to the problem:

Using the general solution we find that $a = 4, b = 13 \Rightarrow a+b = \boxed{17}$ .

When there are 13 bulbs we can turn all switches each in clockwise direction, Hence after 13 flips all bulbs are turned on since each bulb is toggled 3 times in whole process once when it's switch is used and other two times when adjacent switches are used, Thus b=13. When there are 12 bulbs we can flip 1st, 4th, 7th, 10th switches for example ie; grouping them into multiples of three, Thus a=4. Therefore a+b=13+4=17.

The order in which the switches are flipped does not matter, and flipping the same switch twice results in the same configuration. Therefore in a minimal solution, each switch is flipped at most once.

Look at a group of three adjacent lights. The middle light is only affected by the three switches next to those. Therefore, for each group of three adjacent lights, the number of flipped switches in that group must be odd.

Now, look at two groups of three that overlap, forming a group of four lights. The difference between the two groups is the two switches at the ends. But since both groups must have an odd number of flipped switches, the switches on the ends must be in the same position.

In short, every third switch must be flipped, going around the circle, until we reach a switch that is already flipped. If the circle is divisible by 3, we flip every 3rd switch, but otherwise that means we visit (and flip) every switch.

So for n=12 that is 4 switches, and for n=13, 13 switches for a total of 17.