wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Three Locks
        
(Message started by: luke's new shoes on Nov 14^th, 2002, 5:09pm)

Title: Three Locks
Post by luke's new shoes on Nov 14^th, 2002, 5:09pm

three criminals just robbed a bank and go back to their hideout. they put the money behind a high tech secruity door. there are 3 locks on the door, each activated/deactivated by a button next to it. all locks are originally deactivated, and once a lock is activated it is impossible to tell whether it is activated or not. the three criminals want to work out a system so that any two of them can access the money but a single criminal cannot. the 2 criminals accessing the money must be positive that all locks are deactivated otherwise an alarm will sound (and in built lasers will shoot them). Figure out how their system will work.

Title: Re: NEW PUZZLE: three locks
Post by luke's new shoes on Nov 14^th, 2002, 5:42pm

note: each criminal may only give information to one other criminal

Title: Re: NEW PUZZLE: three locks
Post by Pietro K.C. on Nov 15^th, 2002, 10:41am

Hey, cool one! I still haven't got the hang of these information-theoretical puzzles, so it took me a bit of figuring. But how about the following.

Suppose the three locks to be labeled A, B and C, and let the state of a lock (locked, unlocked) be represented by a binary digit (0 = unlocked, 1 = locked). Then the state of the whole configuration can be coded as a binary between 000 and 111.

Also, it should be clear that the action of one of the criminals upon the buttons can be represented by the XOR of the current state with a suitable binary number. For instance, if the locks are at 101, and someone presses buttons B and C, the state goes to 101 XOR 011 = 110.

The cool thing about XOR is that it is equivalent to addition modulo 2; in particular, x XOR x = 0 for any binary x. This is what we shall use.

First of all, each prisoner picks a random binary number between 000 and 111 to be his particular action upon the locks. Then, they each perform their actions in turn. After that, criminal 1 tells criminal 2 what his action is, 2 tells 3 what his own action is, and 3 tells 1 about his. They exchange no further information.

In doing this, any group of 2 criminals will know all three's actions; they can therefore apply them again, and nullify their effects, as per paragraph 4. Notice, however, that any single criminal will lack information about the action of one other criminal, namely the one to whom he passed HIS information. If that single criminal could somehow unlock all 3 locks, he could then deduce the 3rd person's number; but then he would be able to deduce a RANDOM number, which is absurd!

We conclude that this mechanism is sound. It is interesting to notice that any 2 criminals are also able to LOCK the door back up, in such a way that the situation is identical as before! This also follows from the XOR property.

Title: Re: NEW PUZZLE: three locks
Post by Garzahd on Nov 15^th, 2002, 11:00am

I came up with something much simpler... please correct me if I'm misunderstanding something.

Give criminal A the keys to locks 1 and 2, give B keys 2 and 3, give C 1 and 3. Thus each criminal is only giving information to the cohort with whom he's opening the door. The two accessing the vault lock the door behind them, and everything works fine.

Title: Re: NEW PUZZLE: three locks
Post by Pietro K.C. on Nov 15^th, 2002, 11:20am

Well, it seems to me that there are no keys involved...

Quote:

there are 3 locks on the door, each activated/deactivated by a button next to it

Also, the key thing contradicts the following passage:

Quote:

once a lock is activated it is impossible to tell whether it is activated or not

This is important, given that

Quote:

in built lasers will shoot them

:)

But basically, my idea is just an implementation of your policy.

Title: Re: NEW PUZZLE: three locks
Post by Garzahd on Nov 15^th, 2002, 12:26pm

Alright.

To me, it was unclear from the problem statement whether "lock" was defined as "mechanism requiring a key" or "boolean switch". If the latter, then apparently everyone has access to all the keys and Pietro's argument becomes necessary.

Title: Re: NEW PUZZLE: three locks
Post by James Fingas on Nov 15^th, 2002, 1:53pm

To simplify of Pietro's solution, just note that each person only has to press one button (or not press it). Criminal 1 chooses whether or not to press button A, criminal 2 chooses whether or not to press button B, and criminal 3 chooses whether or not to press button C. They can share the information in the same way.

In fact, you technically need only one button! Each person just decides whether or not they'll press it, and shares that information with the next person. Without knowing each person's decision, it is not safe to try and open the door. With three buttons, however, the probability of being able to guess correctly is lower. To make their choice random, they could use Two-Face's coin ;)

Title: Re: NEW PUZZLE: three locks
Post by ZJ on Dec 23^rd, 2002, 5:32am

Its entirely probable that I got the question wrong somehow, or that it has some sneaky twist to it, but if I'm not, and it doesn't, then...well...this puzzle should be put under the Easy category.

[hide]The thieves take turns toggling whatever buttons they want. Thief 1 tells thief 2 his combination, thief 2 tells thief 3, and thief 3 tells thief 1.[/hide]