# Safecracking Puzzle Redux

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?

• What is the starting combination? Jun 21, 2021 at 2:58
• I imagine it doesn’t matter, but let’s assume all the switches are initially at the “low” position just to make things easy. Jun 21, 2021 at 3:37

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.

• 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. Jun 21, 2021 at 5:50
• @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)). Jun 21, 2021 at 6:08