Four buttons on a table

Question

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 1

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

Answer 2

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.

Answer 3

My solution is similar to noedne's.

Equivalently, let's start with all buttons off and the task is to run through every possible configurations. Suppose we have a strategy $S$ for $n=2^k$ buttons and consider the game with $2n$ buttons. First, pair up opposite buttons i.e. always press either none or both of them. This is like playing the game with $n$ buttons - imagine the $2n$ buttons is wrapping around the table with $n$ buttons twice. Applying $S$ (also pressing opposite buttons) would run through all $2^n$ configurations where each pair of opposite buttons has the same state. Call this strategy $S_1$.

Now, we have to change the same/different status of the opposite pairs. There are $2^n$ possibilities (choose same/different for each of the $n$ pairs). Applying $S$ (to any $n$ consecutive buttons) would run through all $2^n$ such possibilities. Call this strategy $S_2$.

So a strategy for $2n$ buttons is: to run $S_1$ $\rightarrow$ do the first step of $S_2$ $\rightarrow$ run $S_1$ again $\rightarrow$ do the second step of $S_2$ $\rightarrow$ run $S_1$ again $\rightarrow$ and so on.

For example, for $n=1$, we do $1$ (using noedne's notation).
For $n=2$, $S_1=11$ and $S_2=10$, so we do $11,10,11$.
For $n=4$, $S_1=1111,1010,1111$ and $S_2=1100,1000,1100$, so we do
$1111,1010,1111,1100,$
$1111,1010,1111,1000,$
$1111,1010,1111,1100,$
$1111,1010,1111$.

More bonus: Show that it is impossible if the number of buttons is not a power of two.

Answer 4

I am not giving a new solution. But I'd like to propose a nicer expression of the solution given for the general case $n=2^k$.

In fact my solution is the same as noedne's.
And the explanation why it works is the same as OHO's.

In the solutions already given the method to explore all states uses the pattern of A, B, A, C, A, B, A, D, ... . The same move A repeats every second move. Between these a second move B repeats every 4 moves, and so on.

You can write it shorter by just writing [D, C, B, A], this notation meaning that you do [C, B, A] then D and [C, B, A] again. [C, B, A] means [B, A] then C then [B, A], and so on. Each list is executed by doing the tail of the list, then the head move, then the tail of the list again.

Using this notation the solution for $n=2^0$ is [x], for $n=2^1$ is [x, xx] and for $n=2^2$ is [x, xx, x.x, xxxx]. The x's and .'s denote resp. a button you switch and a button you don't switch. xx means to switch any two adjacent buttons, x.x means to switch any two buttons separated by a single button you don't touch.

You can continue for $n=2^3$: [x, xx, x.x, xxxx, x...x, xx..xx, x.x.x.x, xxxxxxxx]
and $n=2^4$: [x, xx, x.x, xxxx, x...x, xx..xx, x.x.x.x, xxxxxxxx, x.......x, xx......xx, x.x.....x.x, xxxx....xxxx, x...x...x...x, xx..xx..xx..xx, x.x.x.x.x.x.x.x, xxxxxxxxxxxxxxxx].

As you can see the expression is already much simpler. The last solution expresses a sequence of 65535 moves!

But what is the pattern behind these x's and .'s? To find out you need to write the elements on separate lines and space them a bit. You get:

  x  
  x x  
  x . x  
  x x x x  
  x . . . x  
  x x . . x x  
  x . x . x . x  
  x x x x x x x x  
  x . . . . . . . x  
  x x . . . . . . x x  
  x . x . . . . . x . x  
  x x x x . . . . x x x x  
  x . . . x . . . x . . . x  
  x x . . x x . . x x . . x x  
  x . x . x . x . x . x . x . x  
  x x x x x x x x x x x x x x x x  

Amazingly, hidden in the solution there is a Sierpiński triangle.

So my solution for $n=2^k$ is: produce a Sierpiński triangle of level $k$ and execute the moves using the recursive execution rule given earlier.

The explanation of why it works, as explained by OHO's, is that the bottom part of the triangle explores all $2^{n \over 2}$ combinations of positions without changing the parity of opposing buttons (the bottom left and buttom right triangles are exactly half a turn apart), and the top half explores all $2^{n \over 2}$ possibilities for these parities. The bottom part is executed after every move in the top part, so, the two combined explore all $2^n$ positions.