16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You don't know if the state is "on" or "off" but can you feel the difference between the two positions? Like a lever that could be on the right or on the left (you don't know if "right=on" or "right=off" but you can surely make a difference between right and left)? $\endgroup$ – Arnaud Mortier Mar 6 at 10:12
  • $\begingroup$ @ArnaudMortier I think that not being able to feel "on" and "off" is the essential difference between this and the four cups on a table puzzle. Otherwise, they're the same, right? $\endgroup$ – hexomino Mar 6 at 10:19
  • $\begingroup$ @hexomino I don't know, in the version I know you can touch only two cups per turn. $\endgroup$ – Arnaud Mortier Mar 6 at 10:25
  • $\begingroup$ @ArnaudMortier Ah yes, I forgot that part. $\endgroup$ – hexomino Mar 6 at 10:29
  • 3
    $\begingroup$ @noedne You are right, it is not quite the same. The main question (without the bonus) is however exactly equivalent to the Sliding Bolt Puzzle. $\endgroup$ – Jaap Scherphuis Mar 6 at 12:54
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +1 I felt there was a way to do it inductively but couldn't quite see it. This is still a lot to wrap one's head around. The counting seems to match up with my 4-button if you include the first step of not pressing any button and the general case will take $2^{2^k} - 1$ steps which seems correct. $\endgroup$ – hexomino Mar 6 at 11:21
  • $\begingroup$ Incidentally, does it matter on each $c$ step that the groups of buttons with the zeroes may not always be the same? This is the part I'm having most trouble understanding. $\endgroup$ – hexomino Mar 6 at 11:26
  • $\begingroup$ @hexomino I added a rough explanation. Let me know if it makes sense, and how it could be improved. $\endgroup$ – noedne Mar 6 at 12:04
  • $\begingroup$ The explanation is very helpful, thank you. $\endgroup$ – hexomino Mar 6 at 12:12
  • $\begingroup$ @noedne may I ask how did you get the $m^2 + 2m$ ? $\endgroup$ – Jay Mar 12 at 14:52
22
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think for $n=4$ : $S_1 = 1111, 1100, 1111$ and $S_2 = 1010, 1000, 1010$. If not can yo explain why? $\endgroup$ – Jay Mar 25 at 6:25
  • $\begingroup$ I think your choice of $S_1$ and $S_2$ doesn’t work. Let’s start with all buttons off 0000. The goal is to go through all 16 possibilities after 15 steps. Applying the first six steps (1111,1100,1111,1010,1111,1100) with appropriate table rotations, the table becomes 0000,1111,0110,1001,0011,1100,0000. Note that 0000 appears twice, but this cannot happen because we must go through all 16 possibilities regardless of how the table is rotated. $\endgroup$ – OHO Mar 25 at 18:09
  • $\begingroup$ So how did you get the $S_1=1111,1010,1111$ and $S_2=1100,1000,1100$ for $n=4$, because it is indeed different from noedne's solution for $n=4$ $\endgroup$ – Jay Mar 26 at 14:36
  • $\begingroup$ Start with $n=2$, we have $S=11,10,11$. Then $S_1=1111,1010,1111$ is obtained from duplicating each string in $S$, and $S_2=1100,1000,1100$ is obtained from adding zeros for the second half of each string in $S$. More explanations are included in my answer above. Here are the first few strings for $n=8$. Start with $S$ for $n=4$, $1111,1010,1111,1100,\dots$. Then $S_1=11111111,10101010,11111111,11001100,\dots$ and $S_2=11110000,10100000,11110000,11000000,\dots$ $\endgroup$ – OHO Mar 26 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.