[latexpage]
Problem
You are being held captive in a bunker with no possible way to communicate with any other life form. There is only one way to escape from this prison. You see a wooden box in front of you that has 8 knobs. It looks like the lock of the bunker. Each knob has a pointer that can point in 4 directions: up, right, down or left. On the box there is a note which states: ‘This box can be solved by turning every knob in the upright position, so all 8 knobs must be in the “up” position. This will unlock the bunker for you to escape. However, when turning a knob, the adjacent knobs turn the other way around. For example, when turning knob 4 clockwise, knob 3 and knob 5 turn counterclockwise. To make it a little bit harder, knob 1 and knob 8 are also adjacent to each other. So if you turn knob 1 clockwise, knob 2 and knob 8 turn counterclockwise. On top of that, you can only turn each knob once. When you have solved the puzzle, you are free to escape the bunker, otherwise you are left here for eternity.’
When looking at the box you see that the knobs are in different positions. Here is an illustration:
So knob 1, 2 and 5 are pointing down, knob 3, 4 and 6 are up and knob 7 and 8 are left.
Which knobs should you turn and in which direction to get them all facing up in order to escape the cave?
Hint: Use your OR knowledge to solve this problem, try to think of an objective function and constraints.
Solution
Solving this problem requires some knowledge of linear algebra and operations research. Let $x_i$ be the number of times we turn knob $i$ clockwise. Our objective is to find the minimal number of moves such that all knobs point upwards. We can make a non-linear model to help understand the problem a bit better.
First we have to come up with some constraints for our model. If we look at what happens when for example knob 1 is turned clockwise, we know knob 8 and knob 2 turn counterclockwise. Therefore our left-hand side of the first equation will become something like $x_1$ – $x_2$ – $x_8$, because when we turn knob 1, knob 2 and 8 must be exactly the opposite. Then we move on to the second knob. If we turn this one clockwise, knob 1 and 3 will turn counterclockwise. Therefore the second constraint will be $-x_1$ + $x_2$ – $x_3$. We will do this until we have reached the final knob.
Now we must determine the right-hand side of each constraint. Note that when a knob is turned clockwise 4 times it will be in the same position as it started in. So we need to make sure that our $x_i$ cannot take on a value of 4 because that would be useless. Moreover, a knob that is turned three times clockwise will give the same result as turning the knob one time counterclockwise. Basically what this means is that $x_i$ cannot exceed a value of 2 for all $i$. This will bring us closer to our optimal solution, since our objective is to find the minimal number of turns such that all knobs face upwards.
At last, we need to find out how many times and in which direction each knob must be turned. This is fairly easy to see from the figure above. Knobs 1, 2 and 5 must be turned 2 times clockwise, knobs 3, 4 and 6 must stay in the same position and the last two knobs must be turned once clockwise. Using all of this information we should get a non-linear model that would look like this:
Minimize
\begin{equation}
z = \sum_{i=1}^{8} \mid x_i \mid
\end{equation}
Subject to
\begin{equation}
x_1 – x_2 – x_8 = 4k_1 + 2
\end{equation}
\begin{equation}
-x_1 + x_2 – x_3 = 4k_2 + 2
\end{equation}
\begin{equation}
-x_2 + x_3 – x_4 = 4k_3
\end{equation}
\begin{equation}
-x_3 + x_4 – x_5 = 4k_4
\end{equation}
\begin{equation}
-x_4 + x_5 – x_6 = 4k_5 + 2
\end{equation}
\begin{equation}
-x_5 + x_6 – x_7 = 4k_6
\end{equation}
\begin{equation}
-x_6 + x_7 – x_8 = 4k_7 + 1
\end{equation}
\begin{equation}
-x_1 – x_7 + x_8 = 4k_8 + 1
\end{equation}
And
$x_i$, $k_i$ integer for $i = 1, \ldots, 8$
To solve this model we need to linearize the objective function. We can do so by introducing two new variables $x_i^+$ and $x_i^-$. Where $x_i$ = $x_i^+$ – $x_i^-$ and $x_i^+$, $x_i^- \geq$ 0 and integer. To explain the variables a bit more; $x_i^+$ means that if its value is for example 1, the knob will be turned clockwise once. If $x_i^-$ has a value of 1 it will turn counterclockwise. Now our model can be linearized by substituting every $x_i$ with $x_i^+$ – $x_i^-$. So our objective function would look like this:
Minimize
\begin{equation}
z^* = \sum_{i=1}^{8} (x_i^+ + x_i^-)
\end{equation}
Note that the new objective value is valid since in the optimal solution, either $x_i^+$ or $x_i^-$ equals 0 for all $i$. Now we can actually solve this problem in excel by using the “excel solver”. This will give you the solution to the problem: knob 1 should be turned once clockwise, knob 2 should not be turned, knob 3 should be turned once clockwise, knob 4 should be turned once clockwise, knob 5 should not be turned, knob 6 should be turned once clockwise, knob 7 should be turned once clockwise and knob 8 should be turned once counterclockwise.
What is so interesting about this problem is that it does not seem like an OR problem, but you can certainly use your knowledge of OR to come up with a solution. There are other possible ways to find the solution, but I think it is very interesting to see that we can use our knowledge of modelling to come up with simple solutions to difficult problems.
Credits to Dion Hoek for making the mathematical model for this problem and solving it.
This article is written by Sam Ansari
