TransWikia.com

Sliding Bolt Puzzle

Puzzling Asked by diabonas on January 1, 2021

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)

3 Answers

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

Correct answer by Kendall Frey on January 1, 2021

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!

Answered by Rob Watts on January 1, 2021

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

Answered by thereisnospoon on January 1, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP