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 table. On top of the table, 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. For this, he chooses some of the barrels and presses the buttons. When he is ready, he shouts “Open sesame!”. If all the lamps are on, the cave opens. Otherwise, the table 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 table. I.e. the positions do not turn when the table 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 table 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 table 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 table. 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 table always spins an even number of positions. Our strategy for $2n$ still works. However, solving this size $2n$ table is equivalent to solving two size $n$ tables 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 table with $2n$ lamps, we define its reduction to be a table with $n$ lamps in which the $i$th lamp is on if in the original table lamps $i$ and $i+n$ are in the same state, and it is off otherwise. Observe that rotating the table rotates its reduction. Furthermore, changing the lamps in positions $A_i$ on the original table 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 table changes as we apply the strategy for the full table. 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 table changes as if we were applying the strategy for a table with $n$ lamps. Therefore, after one of these steps, the reduced table 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 table. That is, a table with $n$ lamps in which lamp $i$ is on if and only if lamp $i$ is on on the full table for $i=1,2,...,n$. Observe that rotating the full table rotates the half table. And changing the lamps in positions $B_i$ is the same as changing the lamps in positions $A_i$ of the half table. Therefore, as we apply $B_1,...,B_M$ to the full table, the half table changes as if we were applying the strategy of an $n$-lamp table. Therefore, at some point the half table will have all of the lamps on. It is clear that the full table also has all of the lamps on at that point, and thus we are done.
