logical deduction - Four buttons on a table

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.

Answer

$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.

Induct on $k$.

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., $01011\rightarrow0011001111$).

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., $01001\rightarrow0010001010$).

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.

Explanation:

Think of the $2n$ buttons as being divided into two equal groups of $n$ alternating buttons $A$ and $B$. $A$ and $B$ maintain their relative orientation whenever the table is rotated. We can also form a third imaginary group of $n$ buttons $C$ by xor-ing together neighbors of $A$ and $B$. Whenever $b_i$ is applied to all $2n$ buttons, $a_i$ is applied to $A$ and $B$, and $C$ remains fixed. Whenever $c_i$ is applied to all $2n$ buttons, $a_i$ is applied to $C$. This means that the sequence of button configurations produced comes in $m+1$ groups of $m+1$ where $C$ is preserved within each group and cycled through all $2^n$ states between groups. Within each group, the sequence cycles through the $2^n$ possible configurations of $A$ and $B$ given a certain $C$.