8
$\begingroup$

The brilliant engineers at ACME industries have created what they think is a very secure safe. There are $9$ switches, each with three settings (high, low, and off). However, these engineers are lazy, and only $2$ of these switches actually do anything! The safe will open when a lever is pulled while these two switches are in a certain, secret setting. The "security" of this safe relies on the fact that nobody knows which pair of switches are the functional ones.

The engineers believe that anyone trying to open the safe would potentially have to try all $3^{9}$ possible settings of the switches. Your task: make fools of them by showing how to crack the safe in just $15$ guesses.

Source: Puzzling Adventures, by Dennis E. Shasha.

Additional challenge: What is the fewest number of guesses you need? I don't know the answer.

Improve this question
$\endgroup$
4
  • $\begingroup$ Is a blowtorch considered a guess? ;) $\endgroup$
    – Ian MacDonald
    May 7, 2015 at 22:32
  • 1
    $\begingroup$ Wouldn't it take a mere 324 guesses to brute force this safe, rather than the "brilliant" engineers' 3^9? $\endgroup$
    – Caleb
    May 7, 2015 at 22:48
  • $\begingroup$ If all of the switches mattered, there are 3 options for 9 switches so 3^9 would be the amount needed for testing. $\endgroup$
    – Quark
    May 7, 2015 at 22:58
  • $\begingroup$ @CalebBernard Yes indeed, the engineers are wrong on many levels :P $\endgroup$
    – Mike Earnest
    May 7, 2015 at 23:05

3 Answers 3

Reset to default
8
$\begingroup$

Here's a method to crack the safe in 15 moves:

The three settings can be represented as 0, 1, or 2. The possibilities that can open the safe are then 00, 11, 22, 01, 10, 02, 20, 12, and 21.

Step 1:

Test the combinations of all 9 switches at 0, 1, and 2 for a total of 3 guesses. If none of these work, that eliminates the first 3 potential cases.

Step 2:

Test these cases: (012012012, 120120120, 201201201) and (021021021, 210210210, 102102102). Any two positions chosen that aren't apart by multiples of 3 have every combination tested. If the safe still isn't opened by now, then the two switches are in the same position in the triplet.

Step 3:

Test these cases: (000111222, 111222000, 222000111) and (000222111, 222111000, and 111000222). These cases test all the cases for the switches being apart by multiples of 3. After the last test case (guess #15), every possible combination has been tested for any pair of switches.

Note:

I'm fairly certain 15 is the lowest number of guesses needed to guarantee a solution.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Correct, very well done! $\endgroup$
    – Mike Earnest
    May 7, 2015 at 23:35
  • $\begingroup$ Do you know what the optimal answer is for $n$ switches with $k$ settings, still with only 2 switches doing something? I know that you can get the minimum of $k^2$ if $n \leq k$ and $k$ is prime. $\endgroup$
    – xnor
    May 7, 2015 at 23:59
  • $\begingroup$ It seems like it would depend on other factors like if k is a multiple of n and of course which is bigger. $\endgroup$
    – Quark
    May 8, 2015 at 0:16
  • $\begingroup$ @xnor With $4$ switches, and $3$ settings, you can succeed in $9$ guesses (exercise left to reader). $\endgroup$
    – Mike Earnest
    May 8, 2015 at 0:17
2
$\begingroup$

I think Quark's answer is correct, so I decided to think about a slight variation: what is the quickest way to get into the safe (rather than fewest guesses)? So consider this a bonus answer.

I make 2 assumptions:

  1. moving a switch by 1 position and pulling the "guess" lever both take 1 unit of time.
  2. moving a row of switches that are all in the same position takes the same amount of time as moving just one of them (because you can push them all with your hand at the same time).

Here is my method to get into the safe AQAP: It takes 59 switch flips and 51 lever pulls (pull the lever after every switch except for all 1's, after the first time) for a total of 110 units of time. I think the unit of time would be no more than a second, and so I can get into the safe in 2 minutes tops.

222222222 111111111 000000000 011111111 022222222 122222222 111111111 100000000 200000000 211111111 221111111 220000000 110000000 111111111 112222222 002222222 001111111 000111111 000222222 111222222 111111111 111000000 222000000 222111111 222211111 222200000 111100000 111111111 111122222 000022222 000011111 000001111 000002222 111112222 111111111 111110000 222220000 222221111 222222111 222222000 111111000 111111111 111111222 000000222 000000111 000000011 000000022 111111122 111111111 111111100 222222200 222222211 222222221 222222220 111111110 111111111 111111112 000000002 000000001

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is a whole other can of worms! $\endgroup$
    – Mike Earnest
    May 7, 2015 at 23:47
1
$\begingroup$

The mistake the engineers made is not requiring all other switches to be off at the time the two 'secret' switches are in the correct state. This means that we can test multiple combinations with each pull of the lever. So...

- There are 36 distinct pairs of switches.
- For each pair, there are nine combinations that need to be checked
- (OO, OL, OH, LO, LL, LH, HO, HL, HH)

...which works out to 324 per line. With three guesses, we can cover all the matching pairs for the entire thing:

OOOOOOOOO
 LLLLLLLLL
 HHHHHHHHH
We need only six to make sure all adjacent pairs are covered, and we can do it by solving the first 2 switches and repeating the pattern:

OLOLOLOLO
 OHOHOHOHO
 LOLOLOLOL
 LHLHLHLHL
 HOHOHOHOH
 HLHLHLHLH

...which conveniently hits all the 'odd' non-adjacent pairs; since 1-2 is complete, the repeating pattern means (1-4, 1-6, and 1-8) will be as well. Same for (2-3, 2-5, 2-7, 2-9), but reversed, and the sets continue with (3-4, 3-6, 3-8), (4-5, 4-7, 4-9), (5-6, 5-8), (6-7, 6-9), (7-8), (8-9). That's 20 of the 36 pairs done so far.

Now we make sure the even pairs are OK. Same pattern, but fill each line by skipping one and wrapping once:

OLLOOLLOO
 OHHOOHHOO
 LOOLLOOLL
 HOOHHOOHH
 LHHLLHHLL
 HLLHHLLHH

This gives us (1-3, 1-5, 1-7, 1-9), (2-4, 2-6, 2-8), (3-5, 3-7, 3-9), (4-6, 4-8), (5-7, 5-9), (6-8), (7-9) -- the remaining 16.

EDIT: There's a mathematical way to express this; this was assuming that when cracking the safe, I temporarily become an innumerate monkey. If I can think of it, I'll come back and bolt it on.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Your method doesn't work when the leftmost and rightmost switches are the function ones, and their settings are different. $\endgroup$
    – Mike Earnest
    May 7, 2015 at 23:47

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.