Ryfujk

I was asked lately (in an interview) to solve this puzzle, which is similar to the 4 cups on table puzzle.

In a certain room there is a rotating round table, with 4 symmetrically located indistinguishable buttons. Each button can be either ”on” or ”off”, however one cannot
tell its the current state by its appearance. The room is lighted if and only if all the buttons are all ”on”, and there is nobody inside.

• A person is (repeatedly) allowed to enter the room, and press whichever buttons
she likes. After she steps out, she is told whether she succeeded to put the light
on. At the same time, a table rotates in an unknown manner.

The goal is:
to design a deterministic strategy to put the light on, no matter what is the initial state of the buttons.

As a bonus I was given:
The same above but with: $$n = 2^k$$ symmetrically (with respect to rotation) located buttons.

4-button method

Step 1 - Do not press any buttons, step out
Step 2 - Press all buttons, step out.

If the light is not turned on in either case then we know we are neither in the situation where are buttons are "on" or all lights are "off".

Step 3 - Press any pair of diagonally-opposite buttons, step out.
Step 4 - Press all buttons, step out

If the light is not turned on in either case then we know we are not in a situation where just two diagonally opposite buttons are "on". So now there is either one button "on", two adjacent buttons "on" or three buttons "on".

Step 5 - Press any two adjacent buttons, step out.
Step 6 - Press all buttons, step out.

If we had been in the case of two adjacent buttons and the light is not turned on in either step, we will have changed to the case where two diagonally opposite buttons are "on".

Step 7 - Repeat Step 3
Step 8 - Repeat Step 4

If the light is not on after either step then we must either be in the case where one button is "on" or three buttons are "on".

Step 9 - Press any three buttons, step out
Step 10 - Press all buttons, step out.

If the light has not turned on in either step then we must have now pivoted into a case where two buttons are "on" and two buttons are "off", so we can revert to the strategy we had in that case.

Steps 11 - 16 - Repeat Steps 3 - 8

The light must be turned on at one of these steps.

$n=2^k$ button method

Represent the state of the buttons using an $n$-bit string. Then a sequence of moves is represented by a sequence of $n$-bit strings that we xor with the button states.


Proceed by induction.


If $k=0$, then one possible sequence is $(1)$.


Suppose we have a sequence $(a_1,dots,a_m)$ for $n=2^k$ buttons.


Let $(b_1,dots,b_m)$ be the sequence of $2n$-bit strings where $b_i$ is the result of adding a copy of each bit in $a_i$ after that bit (e.g., $01011rightarrow0011001111$).


Let $(c_1,dots,c_m)$ be the sequence of $2n$-bit strings where $c_i$ is the result of adding a $0$ after each bit in $a_i$ (e.g., $01001rightarrow0010001010$).


Then a sequence for $2n=2^{k+1}$ buttons is the $(m^2+2m)$-length sequence $$(b_1,dots,b_m,c_1,b_1,dots,b_m,c_2,dots,c_{m-1},b_1,dots,b_m,c_m,b_1,dots,b_m)$$ where $m+1$ copies of $(b_i)$ are interleaved with $(c_i)$.


For example, if $(a_i)=(1)$ is a $1$-button sequence, then $(b_i)=(11)$, $(c_i)=(10)$, and $(11,10,11)$ is a $2$-button sequence, and similarly $$(1111,1100,1111,1010,1111,1100,1111,1000,1111,1100,1111,1010,1111,1100,1111)$$ is a $4$-button sequence.