This problem always brings me great memories. My favourite part of working on a puzzle is playing around with it with a group of people. Everyone sharing their ideas. That’s how I first heard about this problem, and that’s why I love it so much.
At the entrance to a cave, there is a rotating round platform. On top of the platform, there are n identical barrels, evenly space along the circumference. Inside each barrel there is a lamp, controlled by a button on the outside. The state of each lamp is unknown, and it cannot be deduced from the outside.
Ali Baba wants to enter the cave, and to do so, he must turn all of the lamps on. He can change the state of the lamps by pressing the buttons, and when he is ready, he shouts “Open sesame!”. If all the lamps are on, the cave opens. Otherwise, the platform starts spinning so fast, that when it stops, it is impossible to tell how much it has turned.
Throughout this solution we will identify the positions of the lamps, and the lamps, with the integers modulo $n$ in the natural way. Notice that the positions are relative to the ground, and not relative to the platform. I.e. the positions do not turn when the platform does.
Our first observation is that $n$ must be even or equal to $1$. For this, let $n\geq 2$, suppose that there is a strategy that allows us to open the door in finitely many attempts, and let $M$ be the maximum number of attempts needed with this strategy, which we take to be minimal. It is not hard to see that $M$ must be at least the number of initial configurations of the lamps, i.e. $M \geq 2^n>2$. A strategy consists of a sequence of sets $A_1, A_2, ..., A_M$, each representing the set of positions of the lamps that are changed in the $i$th step. After $M-1$ steps, if the door hasn’t opened, we are guaranteed that applying $A_M$ will turn all of the lamps on, no matter what the position of the platform is. Therefore, it is clear that $A_M$ is precisely the set of all positions, and the current state of the lamps is all off.
Therefore, after $M-1$ steps the lamps are either all on or all off. Now we look at the platform after $M-2$ steps. If we are not done, then we know that applying $A_{M-1}$ will make all of the lamps equal, regardless of the current position of the platform. Therefore, rotating the current state either has no effect, or it inverts the states of all the lamps. This means that the lamps must alternate being on and off, and hence $n$ must be even as claimed.
The next step is to show that if there is a strategy for $2n$ then there is a strategy for $n$. Indeed, suppose that there is a strategy for $2n$. Additionally suppose that we are told that the platform always spins an even number of positions. Our strategy for $2n$ still works. However, solving this size $2n$ platform is equivalent to solving two size $n$ platforms simultaneously. Therefore we must also have a strategy for $n$ as claimed.
Finally, we show that if there is a strategy for $n$, then there is a strategy for $2n$. This, together with the above and the fact that a single lamp can easily be solved, allows us to conclude that there is a strategy with $n$ lamps if and only if $n$ is a power of $2$.
Suppose that there is a strategy for $n$ lamps, and define $M$ and $A_1, A_2, ..., A_M$ as before. For $i = 1, ..., M$, define
\[B_i = A_i\cup \left(A_i+n \right) = \lbrace a, a+n : a\in A_i\rbrace.\]
We define a strategy for $2n$ lamps as follows:
\[
\begin{aligned}
A_1,\, &B_1,…,B_M, \\
A_2,\, &B_1,…,B_M, \\
&\vdots \\
A_M,\, &B_1,…,B_M.
\end{aligned}
\]
To see why the above strategy works, it will be convenient to introduce the following definition. Given a platform with $2n$ lamps, we define its reduction to be a platform with $n$ lamps in which the $i$th lamp is on if in the original platform lamps $i$ and $i+n$ are in the same state, and it is off otherwise. Observe that rotating the platform rotates its reduction. Furthermore, changing the lamps in positions $A_i$ on the original platform is the same as changing the lamps in positions $A_i$ on the reduction. Finally, changing the lamps in positions $B_i$ on the original has no effect on the reduction.
With the above in mind, let us have a look at how the reduced platform changes as we apply the strategy for the full platform. Clearly the effect of the steps in which the lamps in $B_i$ are changed is just a rotation of the reduction. Thus by only looking at steps $1, M+2, 2M+3,...,M^2$ the reduced platform changes as if we were applying the strategy for a platform with $n$ lamps. Therefore, after one of these steps, the reduced platform will have all of the lamps on.
At this point, opposite lamps are in the same state, and thus it is possible to define the half platform. That is, a platform with $n$ lamps in which lamp $i$ is on if and only if lamp $i$ is on on the full platform for $i=1,2,...,n$. Observe that rotating the full platform rotates the half platform. And changing the lamps in positions $B_i$ is the same as changing the lamps in positions $A_i$ of the half platform. Therefore, as we apply $B_1,...,B_M$ to the full platform, the half platform changes as if we were applying the strategy for an $n$-lamp platform. Therefore, at some point the half platform will have all of the lamps on. It is clear that the full platform also has all of the lamps on at that point, and thus we are done.
