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:
- 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)
Answer
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:
$$ \begin{array}{c|ccc} & \fbox A & \fbox B & \fbox C\\ \hline 1 & 2 & 3 & 4\\ 2 & 1/3/4 & 2 & 2\\ 3 & 2 & 1/4 & 3\\ 4 & 2 & 3 & 1 \end{array} $$
No comments:
Post a Comment