Steps to turn on $2^n$ lamps on a roulette wheel

combinatorics

There are $2^n$ lamps on a roulette wheel. Each time player A decides
on a list of lamps to flip (so on becomes off and off becomes on).
Player B sees player A's list, and rotates the roulette wheel to a
different location. Player A still flip the lights as if they were on
the original location. For example, say there are four lights
$1,2,3,4$. Player A decides to flip the switch of lamp $1$. Player B
rotates the wheel to $3,4,1,2$. Then after this round, lamp $3$ is
flipped.

At the beginning, some lamps are on and some are off. Prove that regardless of the initial state, for no more than
$2^{2n}$ rounds, player A can always turn on all the lights.

There is a hint to this problem. Prove by mathematical induction. Suppose there is a way for $2^{k}$ lamps. Consider the case when $2^{k+1}$. Pair up the lamps that are opposite of each other…

I am thinking after we pair up the lamps that are opposite of each other, We define a new state for this $2^{k}$ pairs. If the pair has different states, we treat them as an "off" lamp. Otherwise we treat them as an "on" light. But there is no way to turn on this "off" light in this new, paired up roulette. My idea could be completely off.

Certainly, a solution without using this hint is welcome too.

Best Answer

It looks to me that you've made significant progress. Before reading further, I encourage you to push through from what you have, with the knowledge that your path does indeed lead to a solution. In fact, my solution is just what you have and what's in the comments.

If you want to read further, scan through the hints as a suggestion, before reading in more detail.

I also provided some motivational steps that hint we're proceeding in the right direction. These obviously could be skipped when writing up an actual solution.

Hint 1: Consider the last step: What possible state could A be in which guarantees no matter what B choses, A will win?

The only state is where all lamps are off, and A chooses all lamps to be turned on. Then, no matter what B does, A will win.
Conversely, given any state where some lamp is on, B can rotate so that it is turned off, so A will not win (yet).

Observation: This step is unique. It suggests that we can push this train of thought further.

Hint 2: Consider the second last step: How can A get to the last step.

One possible approach is that every other lamp is on, and A decides to turn on every other lamp. Then, if B lands on an on lamp, A turns all of them off (getting us to the last step). If B lands on an off lamp, A turns all of then on (and is done).

Note that this approach isn't unique, for example the pattern could be "on on off off, ..... " so we might not be able to backtrack further.

However, what do these approaches have in common? It seems like the diametrically opposite lamps have to be the same state.
In fact, we can show that if a state has diametrically opposite lamps that are on/off, then we cannot reach an "all on" or "all off" state. (How?)

So, this line of reasoning indicates that we likely really want to get to "diametrically opposite lamps are both on or both off".

Hint 3: Setting up the induction.

Given $2^{k+1}$ lights, we'd call it scenario X.
We construct scenario Y with $2^k$ lights as follows:
- If lights $i, 2^k + i$ of X are in the same on/off, then light $i$ in Y is on.
- If lights $i, 2^k + i$ of X are in different on/off, then light $i$ in Y is off.

Fill in this gap: If A wants to turn on lamps 1 and 3 in Y, what is the equivalent sequence in X?

Hint 4: Run the induction, see what we get.

No matter what the $2^k$ lamps in Y are, after at most $2^{2k}$ steps we can get them to all on.
Running the equivalent sequence on X, we get that lamps $ i, 2^k + i$ are all both on/off. Call this X'.

Obviously this isn't sufficient, or is it?

Hint 5: Setup the induction again.

Now, after $2^{2k}$ steps, X' has $2^{k+1}$ lights that are matched up with their opposite partners. We construct scenario Z with $2^k$ lamp in the following manner:
- Lamp $i$ in X' has the same on/off as lamp $i$ scenario Z for $1 \leq i \leq 2^k$.

Fill in this gap: If A wants to turn on lamps 1 and 3 in Z, what is the equivalent sequence in X'?

Hint 6: Run the induction again.

No matter what the $2^k$ lamps in Z are, after $2^{2k}$ steps we can get them to all on.
This means that lamps $ i$ and $ 2^k + i$ for $ 1 \leq i \leq 2^k$ in X' are all on.

Hence, we are done.

Bonus: Note that in the induction, if $2^k$ lamps takes $f(k)$ steps, then $2^{k+1}$ lamps takes $2f(k)$ steps. Since we can easily verify that $2^0$ lamps takes (at most) $1$ step, we can conclude that $f(k) = 2^k$ steps, which is much better than the $2^{2k}$ steps that they gave us.

Related Question