18
$\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 '19 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 '19 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 '19 at 10:25
  • $\begingroup$ @ArnaudMortier Ah yes, I forgot that part. $\endgroup$ – hexomino Mar 6 '19 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 '19 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$.

| improve this answer | |
$\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 '19 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 '19 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 '19 at 12:04
  • $\begingroup$ The explanation is very helpful, thank you. $\endgroup$ – hexomino Mar 6 '19 at 12:12
  • $\begingroup$ @noedne may I ask how did you get the $m^2 + 2m$ ? $\endgroup$ – Jay Mar 12 '19 at 14:52
23
$\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.

| improve this answer | |
$\endgroup$
2
$\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.

| improve this answer | |
$\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 '19 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 '19 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 '19 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 '19 at 17:19
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$

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.