54
$\begingroup$

You are in a room with two adjacent doors locked by four sliding bolts. The bolts are movable and block only one door at a time; however, you do not know which bolt currently is blocking which door.

An example configuration:

two doors blocked by four sliding bolts (example configuration)

Luckily, there are three buttons A, B, C, which cause some bolts to slide from the door they are curently blocking over to the other door. However, each button can trigger different actions, which one is used is determined at each push in a fully random way:

  • Button A slides at random either
    • bolt 1 or
    • bolt 2 or
    • bolt 3 or
    • bolt 4.
  • Button B slides at random either
    • bolt 1 and 2 or
    • bolt 2 and 3 or
    • bolt 3 and 4 or
    • bolt 4 and 1.
  • Button C slides at random either
    • bolt 1 and 3 or
    • bolt 2 and 4.

Your task is to find a sequence of button activations to get out of the room (i.e., to move all the bolts to one door so the other one is open) regardless of the unknown initial position of the bolts. (You may try the doors after each touch of a button to see whether they are open.) The sequence should be as short as possible.

Source: Newsgroup de.rec.denksport, Zwei Tueren, vier Riegel, GJ Woeginger, 2011-10-15 (German)

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Are we allowed to try opening the doors before finishing the sequence? $\endgroup$
    – Kendall Frey
    Commented May 14, 2014 at 23:52
  • 2
    $\begingroup$ @KendallFrey Good point, you are allowed to try after each touch of a button, otherwise the puzzle wouldn't have a solution: it can be shown that there is no sequence where the door is guaranteed to be open after the last action. I have edited the question accordingly. $\endgroup$
    – diabonas
    Commented May 15, 2014 at 12:54
  • $\begingroup$ Is there a better way to treat this as an integer sequence than transforming to the 4-digit binary number 0000..1111? then e.g. a:x -> one of {x ^ 0001, x ^ 0010, x ^ 0100, x ^ 1000} ? i.e. randomly transform to one of the four neighbors on a four-variable Karnaugh map? $\endgroup$
    – smci
    Commented Jan 15, 2015 at 21:35
  • $\begingroup$ This is puzzling.stackexchange.com/questions/80329/… in disguise. $\endgroup$
    – Florian F
    Commented May 27, 2020 at 8:15

3 Answers 3

Reset to default
41
$\begingroup$

C B C A C B C, trying the doors at each step.

There are 4 possible states of the bolts:

1. All on one door. It is possible to get out.
2. Exactly one bolt is on one side.
3. Bolts {1, 2}, {2 ,3}, {3, 4} or {4, 1} are on one side.
4. Bolts {1, 3} or {2, 4} are on one side.

Initially we can be in states 2, 3, or 4. These are the possible states after each step. (We first try both doors to make sure we aren't in state 1.)

C: 2 or 3

B: 2 or 4

C: 2

A: 3 or 4

C: 3

B: 4

C: 1 (We will definitely have escaped by now)

Here's the state transition matrix I used to calculate the answer:

A B C
1 2 3 4
2 1/3/4 2 2
3 2 1/4 3
4 2 3 1
Improve this answer
$\endgroup$
1
  • $\begingroup$ Great answer! Now that the puzzle is established, I have asked a follow-up question regarding the best solution in terms of expected opening time I'm interested in (and haven't found an answer for yet). $\endgroup$
    – diabonas
    Commented May 15, 2014 at 13:34
14
$\begingroup$

This is a supplemental to Kendall's answer that proves its correctness:

Because there are four bolts, each with two possible positions, there are 24=16 states. You might think we'd want to categorize the states by the number of bolts that are currently blocking one of the doors, but that won't really help us. What we want is to group all possible states by how they react to a button press and what state it leaves them in.

I'd suggest that instead of thinking of the bolts being arranged vertically, we think of them as being arranged in a circle:

 1
4 2
 3

So now the buttons have these behaviors:

  • Button A: slide a random bolt
  • Button B: slide two adjacent bolts
  • Button C: slide two opposite bolts

This makes it easier to see what our states should be

  • State 1: All in one door. This lets us leave, so we wouldn't be pushing buttons anymore.
  • State 2: One bolt (I'll call it the odd one) is different from the others
  • State 3: Two bolts are in each door, with the two bolts in a door being next to each other
  • State 4: Two bolts are in each door, with the two bolts in a door being opposite each other

Now consider what can happen at each state (other than 1) when a button is pushed:

  • State 2:
    • Button A:
      • We get lucky and the odd bolt slides, taking us to state 1
      • A bolt next to the odd bolt slides, taking us to state 3
      • The bolt opposite the odd bolt slides, taking us to state 4
    • Button B:
      • The odd bolt and a bolt next to it slide, leaving us in state 2
      • Two other bolts slide to join the odd bolt, still leaving us in state 2
    • Button C:
      • The odd bolt and the bolt opposite it slide, leaving us in state 2
      • The two bolts next to the odd bolt slide, leaving us in state 2
  • State 3:
    • Button A:
      • One of the pairs will be disrupted, taking us to state 2
    • Button B:
      • We could get lucky and have one of the pairs slide, taking us to state 1
      • One from each pair will slide, taking us to state 4
    • Button C:
      • One from each pair will slide, leaving us in state 3
  • State 4:
    • Button A:
      • One pair will be disrupted, taking us to state 2
    • Button B:
      • One from each pair will slide, taking us to state 3
    • Button C:
      • One of the pairs will slide, taking us to state 1

So based on this, here's the state transition matrix:

A B C
2 134 2 2
3 2 14 3
4 2 3 1

Note that this is exactly the transition matrix Kendall came up with, with the row for state 1 removed. Also, we see that if we are in state 4, then pushing button C will always get us out, and if we are in state 2 or 3 then pushing the button doesn't change what state we are in. Also, if we are in state 2, then pushing either B or C will not change what state we are in.

Suppose we were told that we were in either state 3 or 4. What would we do? Well, if we push button C we will get out if we were in state 4. If we're still not free, then we'd know that we had been in state 3, and since button C doesn't affect that then we know we are still in state 3. Then we could push button B, either freeing us or taking us to state 4. From state 4 we can push button C again to get free.

So if we know we are in state 3 or 4, we should push C, then B, then C (checking after each button push). This guarantees that we will be able to get out by the third button push at the latest.

What if we did that while we were in state 2? Since buttons B and C don't change us out of state 2, we would still be in state 2! So if we don't know what state we are in, we push CBC and are either free, or started in state 2. If we started in state 2 then we would still be in state 2. Then, we can push button A. Pushing button A from state 1 will take us to one of the other states. If we aren't free, then we'll know we are now in state 3 or 4. We covered this already though, so we know we should hit CBC again and we'll be free!

So that's why the pattern CBC A CBC will always allow us to escape. Just remember to check after each push, because the first press of the button C might be what allows us to escape!

Improve this answer
$\endgroup$
4
$\begingroup$

I know it's a year old question, and has already been solved, still I gave it a swing. I see the other answers have used transition matrix, which I have no idea what that is. I solved it in kind of a different way. Maybe in principle does the same, but what the heck, I spent hours on it, and I want to share it! Sorry if the image is too messy, but I hope it manages to get the idea across.

It's kind of messy, but I guess you'll get how I reached the solution using the flowchart thing.

So at each step I basically chose the button that had the best chance to arrange the bolts in a way that the door is able to open. For example, out of the four initial states, pressing "C" would open the door if it was state no. 3, for sure. Pressing "A" could open if it was state no.1 but not for sure. Pressing "B" could open if it was state no. 2 or 4, but again, not for sure. This way I was able to eliminate the case of initial state 3. Similarly I chose the buttons at each step in a way that would eliminate most of the possibilities. (I hope I'm making sense, if not please discuss if interested.).

This way the solution came out to be, as stated by other answers,

C>B>C>A>C>B>C

(check the door after each step.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ As Rob Watts stated, there are actually 16 possible states.  He and Kendall Frey have reduced those 16 states to 4 state groups for analysis.  By using four states without defining them, you lead us to assume that you are incorporating the definition that Kendall presented and Rob restated — but you aren’t!  Your states #1, #2, and #3 are actually states 2, 3, and 4 (in the established terminology).  Your state #4 is actually also state 3 (“Two bolts are in each door, with the two bolts in a door being next to each other”), i.e., the same as your state #2. $\endgroup$
    – Peregrine Rook
    Commented Jun 27, 2017 at 18:08
  • $\begingroup$ Also, as far as I can tell, you haven’t solved the puzzle; you have just taken the solution and rationalized that it works.   (If you found C⋅B⋅C⋅A⋅C⋅B⋅A on your own, without copying it from the other two answers, please explain how you did it.)   And, if you spent hours on this, it would have been nice if you had taken another ten minutes and re-drawn the drawing, showing clearly what you want to show, without any cross outs. $\endgroup$
    – Peregrine Rook
    Commented Jun 27, 2017 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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