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:
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:
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)
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:
This makes it easier to see what our states should be
Now consider what can happen at each state (other than 1) when a button is pushed:
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.
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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP