3
$\begingroup$

This is a follow-up to the excellent safecracking puzzle based on me misreading the problem. :-)

You have a safe with four switches, each of which can be in one of three states (low, medium, high). Only two of those switches actually do anything; the other two don’t control the safe. As soon as the two correct switches are set to the right values, the safe pops open.

Your goal is to open the safe with as few switch changes as possible. For example, changing the switches from the (low, low, low, low) to (medium, low, low, low) counts as changing one switch’s value. Moving from (low, low, low, low) to (high, low, low, low) counts as two switch changes, since in moving the first switch from low to high we pass through the state of having the first switch set to medium.

What is the fewest number of switch changes that need to be made to guarantee that the safe will open?

Improve this question
$\endgroup$
2
  • $\begingroup$ What is the starting combination? $\endgroup$
    – Dmitry Kamenetsky
    Jun 21, 2021 at 2:58
  • $\begingroup$ I imagine it doesn’t matter, but let’s assume all the switches are initially at the “low” position just to make things easy. $\endgroup$
    – templatetypedef
    Jun 21, 2021 at 3:37

1 Answer 1

Reset to default
4
$\begingroup$

It can be done in

18

     0000
     0001
     0002
     0012
     0022
     0122
     0222
     1222
     2222
     2221
     2220
     2210
     2200
     2100
     2000
     1000
     1100
     1110
     1111

It takes at least

18

Proof

Each pair of switches must run through all 9 states. This requires at least 8 changes of a switch in the pair. There is a switch with the lowest number k of changes. All others must have at least max(k,8-k) changes. The minimum total number of changes is 16 at k=4. The next best attained by the solution given above is 18 at k=3. Each switch must become 2 at least once. There is one which is last to become 2 for the first time (at step n, say). As all pairwise combinations must be covered all other switches must become 0 at or after step n. By definition of n they all have been 2 already at this time, so they started at 0 went to 2 and back to 0 using up four steps each. But the state (0,0) occurs twice in each pair between two of these three switches. Consequently, at least two of the three switches involved require at least another change to cover all 9 combinations in each pair they participate in. We therefore are at least 2 above 16.

As the lower and upper bounds are equal the number

18

is exact.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are you sure that you visit the required states here? I wrote a brute-force program that visits the 9 states from the answers in the linked question and I get a minimum of 25 steps. I have tried 3 different variants for 9 states and each one gives me 25 steps as minimum. $\endgroup$
    – Dmitry Kamenetsky
    Jun 21, 2021 at 5:50
  • 2
    $\begingroup$ @DmitryKamenetsky The tasks are just different. In Python, you can check my solution (call it x) using the single line all(len({*zip(*p)})==9 for p in itertools.combinations(zip(*x.split()),2)). $\endgroup$
    – loopy walt
    Jun 21, 2021 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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