Friday, May 01, 2009

Friday Fun: Rapidly Rotating Electronic Lock

Circular Electronic LockIt's Friday and you are looking forward to the weekend, but an evil genius has locked you in a room. The door to the room is protected by a special electronic lock with four identical buttons equally spaced along the rim of a circular dial.

Each button toggles an internal switch within the mechanism. You can attempt to open the lock by simultaneously pressing any set of the 4 buttons which will toggle the corresponding switches. If you are lucky enough to thereby align the switches so they are all on or all off, the lock will open. Otherwise the dial begins a spinning cycle that lasts for 1 full minute. When it comes to rest you have no way of knowing which button(s) you pressed previously.

Your captor is returning in 15 minutes. Is there any possible method you can think of that will GUARANTEE that you can open the lock in less than 15 tries? If it is not possible, then let me know why that is the case... so I don't waste my time.
Posted by Blaine at 12:34 AM
Labels: ,

16 comments:

  1. A very interesting puzzle. Thanks.

    If the lock didn't spin, it could be unlocked in 7 or less trys, or go from one locked condition to the other in 8 trys. In that case the combination would be something like 32,34,31,38.

    With the spinning lock, this and simpler combinations applied twice work. The most tries it took me was 13. The fly in the ointment is that how the combination is entered isn't all that obvious, but easily stated.
    ReplyDelete
  2. Can you explain your notation of "32,34,31,38"? I'm not getting how that relates to the buttons.
    ReplyDelete
  3. 3,2,3,4,3,1,3,8 is more like it. In binary the 1's of each number show the combination of buttons of the STATIC lock to be pushed. The button positions (top, bottom, left, right) are given labels of 1,2,4,8. 3 means push buttons 1 and 2. 2 means push button 2, etc.

    In programming terms, I am subjecting an unknown 4 bit number (the lock) to eight successive exclusive-or masks (the combination numbers). Success comes with 0000 or 1111.

    For the ROTATING lock, the labels remain the same as before (ignore the fact that the buttons have changed.) What apparently has changed is that more than 1 application of the 8 masks is required.

    My solution is not backed by any rigor, simply by limited testing.

    The fun part of this is that I was involved in the development of keyless hotel locks.
    ReplyDelete
  4. If the lock spins after an incorrect attempt, and you don't know which buttons you just pushed, how could you ever "guarantee" that you'll unlock it in any number of tries? Every attempt would be equally as much of a complete guess as the last one.
    ReplyDelete
  5. Hugh, I think your method can work randomly, but I don't think it will guarantee the lock will open. Let's imagine that buttons 1 and 2 (top and bottom) had different states (one on, one off). On odd turns, let's say the dial always aligned so you were toggling these between 01 and 10 (still locked). For the even turns, let's imagine that you only ever got one of the untouched switches (4 or 8, left or right) to rotate to the place were you were toggling a single button (4,2,1,8 respectively in your example). Then you'd never be affecting the state of switch 1 and 2 separately to unlock the lock, correct?
    ReplyDelete
  6. More testing has proved to me that my approach doesn't guarantee success. Maximum tries went from 13 to 21. I didn't really answer your question anyway. I was operating on the basis that the system would have to unlock a STATIC lock as well as a ROTATING lock. Now I have to try to understand whether you just proved that there is no sure way to open the lock in time, or...?
    ReplyDelete
  7. I'm amazed. You still won't get a proof from me, but I redid my spreadsheet to automate the rotation, and redid the masks, six of them, taking your hints.

    So far no lock has failed to open in time, both rotating and static.

    Once I would have written a program, but now I have fun abusing applications. I am interested in the proof if you don't think its beyond me.
    ReplyDelete
  8. Blaine, thanks for the excellent puzzle. I propose the following solution and proof... and I look forward to having my logic shot-down :)

    SummaryThe door can be opened in 8 tries... or only 7 tries if you assume that the lock cannot begin in the "open" position.

    NotationDescribe the internal switches using binary notation (e.g. 1001 means that the first and last switch are on). Binary compliments (e.g. 1001 and 0110) are equivalent, since button pushes toggle the switches (instead of changing them to be absolutely on or off) and because both 0000 and 1111 are solutions. Stated another way, the state of a single switch doesn't matter, only the pattern of the states.

    Use the same notation to indicate button pushes; an arbitrary scheme could be used to assign each bit to a particular button (like start with the "North" button and continue clockwise, so 1001 represents pushing the North and West buttons); but as will be shown below, the specific bit-to-button mapping scheme is not important. Furthermore, complimentary button pushes are equivalent (e.g. 1001 and 0110 will yield equivalent results on the switches).

    ClassificationIgnoring compliments, there are 8 possible patterns of switches and of toggles (0000 0001 0010 0011 0100 0101 0110, and 0111). The patterns can be grouped into the following classifications:
    A: patterns with one matching bit and three non-matching bits (0001 0010 0100 0111)
    B: patterns with two adjacent matching bits (0011 0110)
    C: patterns with alternating bits (0101)
    D: patterns with all bits the same (0000); this is the combination of switches which opens the door

    RotationThe rotation of the dial can be seen as "rotating" the bit pattern of the switches. If the switches are labeled 1234, they could stay as 1234 or become 2341, 3412, or 4123. Critically, rotation will never change the classification of a pattern. Hence, an A will remain an A, a B will remain a B, etc. For example, 0001 could rotate one position to become 0010 (an A to an A) or 0011 could rotate two positions to become 1100, which is equivalent to 0011 (a B to a B). This is why the exact mapping of button pushes to the dial is arbitrary.

    Effects of applying each pattern of button pushes to each pattern of bitsConsider applying an "A" button push to a "B" pattern of switches. By considering the possible combinations, it is easy to see that this can only result in an A switch pattern (0001+0011=0010, 0010+0011=0001, 0100+0011=0111, 0111+0011=0100, 0001+0110=0111, 0010+0110=0100, 0100+0110=0010, and 0111+0110=0001). Following this approach, the following table can be constructed (the example is indicated with a *). This really isn't as tedious as it sounds!

    button push pattern A turns switch pattern:
    A -> B or C or D, depending on the specific pattern
    B -> A (*)
    C -> A
    D -> A

    button push pattern B turns switch pattern:
    A -> A
    B -> C or D, depending on the specific pattern
    C -> B
    D -> B

    button push pattern C turns switch pattern:
    A -> A
    B -> B
    C -> D
    D -> C

    button push pattern D turns switch pattern:
    A -> A
    B -> B
    C -> C
    D -> D

    SolutionThe system could start in either switch pattern A, B, C, or D. The following solution will guarantee that pattern D is reached.
    1) button pattern C (A->A, B->B, C->D [solved], D->C), leaving A, B, or C switch patterns
    2) button pattern C (A->A, B->B, C->D [solved]), leaving A or B switch patterns
    3) button pattern B (A->A, B->C or D [solved]), leaving A or C switch patterns
    4) button pattern C (A->A, C->D [solved]), leaving only A switch pattern
    5) button pattern A (A->B or C or D [solved]), leaving B or C switch pattern
    6) button pattern C (B->B, C->D [solved]), leaving only B switch pattern
    7) button pattern B (B->C or D [solved]), leaving only C switch pattern
    8) button pattern C (C->D [solved]), solving the puzzle

    Note that if starting in a D pattern is not possible, then step 1 can be skipped.

    As an interesting aside, I believe that a 3-button door would have no guaranteed solution.
    ReplyDelete
  9. After automating some more, and speeding things up, I see my eyeball fixes aren't working. Like one of my profs said, "Have theory behind your actions." Turns out that I've been having only a 90% to 93% success rate. Still flubbing around is still better than doing nothing in order to escape. I'll try putting Phil's analysis to work. This is fascinating. I'm close to obsessed.
    ReplyDelete
  10. Thank you Phil! I was afraid my spreadsheet might have had a problem. Runs of 4000 trials on each type of lock opened every time. (Just being fussy.)
    ReplyDelete
  11. I also thank Phil for explaining how what I think is termed an "invariance" can be put to practical use. The term was mentioned in passing to me but I never caught on.
    ReplyDelete
  12. Phil has the intended solution. Just to reiterate, in case the mathematical notation got hairy for anyone:

    There are sixteen possible states for the buttons (2 choices for each of 4 buttons = 2 x 2 x 2 x 2 = 16).

    Of these two are the winning state of all off (0000) or all on (1111).

    You can divide the remaining states into three groups, based on their similarity, ignoring rotation.
    State A (every other button pushed):
    0101, 1010

    State B (two adjacent buttons are pushed):
    0011, 0110, 1100, 1001

    State C: (one button is different from the other three):
    0001, 0010, 0100, 1000, 0111, 1110, 1101, 1011

    The winning states are 0000 and 1111. At the outset you are in situation A, B or C though you don't know which.

    Step 1) Push buttons on *opposite* sides of the dial:
    If you were in A, the lock opens!
    If you were in B, you're in B again.
    If you were in C, then you are still in C

    Step 2) Push two *adjacent* buttons:
    If you were in B, the lock opens, or you switch to A.
    If you were in C, then you are still in C

    Step 3) Push two *opposite* buttons:
    If you were in A, the lock opens!
    If you were in C, then you are still in C

    If you are not free by this point, you know you are in C.

    Step 4) Push any *single* button. This will switch you to A or B.

    Now repeat the above steps.

    Step 5) Push buttons on *opposite* sides of the dial:
    If you were in A, the lock opens!
    If you were in B, you're in B again.

    Step 6) Push two *adjacent* buttons:
    If you were in B, the lock opens or you switch to A.

    Step 7) Push two *opposite* buttons:
    You had to be in A, the lock opens!

    So in a maximum of 7 minutes you will have opened the lock.

    P.S. I suppose there is the possibility you started in an unlocked state of 0000 or 1111 at the beginning. If that is allowed, just add a Step "0" where you don't press anything (or press everything) and see if the lock opens.

    Answer:
    Yes, you can guarantee you'll open the lock after 7 tries, if you follow the steps above.
    ReplyDelete
  13. P.P.S. Oh, and and step 4, there's the possibility you open the lock. I forgot to mention that. But if not, you continue to steps 5 and later.
    ReplyDelete
  14. P.P.P.S. And if you are comparing this to Phil's solution I labeled my states slightly differently. Essentially A and C are swapped in the two solutions.
    ReplyDelete
  15. With my interpretation of Phil's solution, I am having a problem agreeing with his summary statement which is correct except for the stated start condition. If the lock begins in the open D, (all same), state, it will always open again on the second try after entering his first two C,(alternating), patterns. It appears to be the A,(single bit), patterns that about 12% of the time require 8 attempts. I'm continuing to play with this. Even with the answers I find the puzzle interesting. (Even if I am my own worst puzzle.)
    ReplyDelete
  16. What I was trying to convey was that if you exclude "D" as a starting position, then you can skip the first step (i.e. only use steps 2-8) and you have a 7-step solution. In either case, the longest solution always occurs on the lock that started in an "A" position. So including D doesn't mean that D is solved in the last step, only that it requires an extra step early on to eliminate it. I'm not sure off-hand if my solution is optimal.

    You might also investigate what happens with more or less buttons. I think (but haven't proven) that a three-button lock can never have a guaranteed solution in a finite number of tries; I haven't looked at more buttons.
    ReplyDelete

Subscribe to: Post Comments (Atom)