9
$\begingroup$

This is a follow-up question for the Sliding Bolt Puzzle. If you have not solved it yet, you might want to head there first, as the extended discussion of its solution in this question will contain spoilers.

In the original version of the Sliding Bolt Puzzle, I asked for the fastest sequence in terms of the maximum number of button presses it takes to definitely open the door, which was given in the accepted answer. However, I was wondering whether there might be a sequence which, while having more button presses, is still faster time-wise when you take into account the probability of the unknown initial position.

To explain a bit more what I mean: As Kendall Frey explained, there are four possible states of the bolts, numbered 1 to 4. (We will neglect state 1 as an initial position, because it is specified that the door is locked at first.) However, these four states are not equally probable as an initial position: The probabilities are

  • 8/14 for state 2,
  • 4/14 for state 3,
  • 2/14 for state 4.

(obtained by simply listing all 16-2=14 possible initial configurations and categorizing them accordingly).

So we see that state 2 is by far the most probable one; the sequence CBCACBC will open it after four touches of a button at the earliest, while the most improbable state 4 will be opened directly.

Hence, my question is: Which is the sequence with the smallest expected value E[t], where t is the number of button pushes until the door opens, taking into account the probability distribution of the initial configuration?

Note that there is also some randomness regarding the next state when you press button A while in state 2 or button B while in state 3 (see the transition state matrix in the accepted answer), which should also be considered.

$\endgroup$
5
$\begingroup$

There are $2^4-2=14$ initial configurations.

Initial cases are described as: $(13)$ means 1 and 3 are on the left door while 2 and 4 are on the right.

  • By playing C first, you eliminate 2 cases: $(13)$ and $(24)$

  • B: removes 2 cases: $(23)$ and $(14)$ or $(12)$ and $(34)$

  • This continues the whole way so that every move removes two of the initial states until all 7 moves remove 14 original states.

One can easily show that there does not exist a single move that can remove more than two initial states at a time. There is also no move that can make initial states equivalent without removing them besides the initial states that are equivalent from the start. (note that because you have two doors, you are really manipulating linked pairs of initial states). This means that the fewest moves solution you already have is, unfortunately for my curiousity, the fastest solution as well.

$\endgroup$
  • $\begingroup$ Note that this means Ross is correct but this only attempts to provide an exact reason why this is the case. $\endgroup$ – kaine May 21 '14 at 20:57
2
$\begingroup$

I think Kendall Frey's solution is the best you can do.

The original CBC is needed to make sure you started in state 2 (and are still there).
Then, after the A, you know you are in state 3 or 4 and don't need A again.

If you do the A earlier, it:
- 25% chance Solves state 2
- 75% chance Puts you in state 3 or 4

Unfortunately, you didn't know you were in state 2, so it could take you from 3 or 4 to 2 instead.

$\endgroup$
  • $\begingroup$ You are right that using A while in state 3/4 will get you into state 2, but still, this might take a shorter while to open the door: if you use CBCACBC, you will be finished in at most 3 button pushes with a mere possibility of (2+4)/14, but will need more than that with a probability of 8/14. If you use e.g. ACBCACBC, you are finished in at most 4 pushes with an increased probability of 8/14, so the expected value for the number of button pushes may be lower because you are more likely to finish earlier. (If I have calculated correctly though, it isn't, but I hope my point became clear.) $\endgroup$ – diabonas May 15 '14 at 16:30
-1
$\begingroup$

My algorithm is more likely to work more quickly than those listed. However since the button is random no algorithm is 100% sure to solve the puzzle.

Is the number of Doors on a side odd?
if yes Push A;

Is there a single gap between the two doors on a side? if yes Push C and Win.

Otherwise Push B;

This can solve some scenarios in 1 iterations if your lucky. However since there is not guaranteed solutions each loop increases the odds of winning. See the original sliding bolt problem for my issue with the solution. The idea of going for fastest when no solution can be guaranteed makes this question difficult to answer.

$\endgroup$
  • 2
    $\begingroup$ You don't know how many locks are in a given configuration, you only know if a door can be opened or not. The solution given in the previous question works. $\endgroup$ – Taemyr Oct 9 '14 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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