Author |
Topic: Three Locks (Read 3179 times) |
|
luke's new shoes
Guest
|
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.
|
| « Last Edit: Sep 1st, 2003, 7:37pm by Icarus » |
 IP Logged |
|
|
|
luke's new shoes
Guest
|
 |
Re: NEW PUZZLE: three locks
« Reply #1 on: Nov 14th, 2002, 5:42pm » |
 Quote  Modify
 Remove
|
note: each criminal may only give information to one other criminal
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
|
Re: NEW PUZZLE: three locks
« Reply #2 on: Nov 15th, 2002, 10:41am » |
Quote Modify
|
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.
|
| « Last Edit: Nov 15th, 2002, 10:41am by Pietro K.C. » |
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: NEW PUZZLE: three locks
« Reply #3 on: Nov 15th, 2002, 11:00am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: NEW PUZZLE: three locks
« Reply #4 on: Nov 15th, 2002, 11:20am » |
Quote Modify
|
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.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Garzahd
Junior Member
Gender:
Posts: 130
|
|
Re: NEW PUZZLE: three locks
« Reply #5 on: Nov 15th, 2002, 12:26pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: NEW PUZZLE: three locks
« Reply #6 on: Nov 15th, 2002, 1:53pm » |
Quote Modify
|
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 
|
| « Last Edit: Nov 15th, 2002, 1:54pm by James Fingas » |
IP Logged |
Doc, I'm addicted to advice! What should I do?
|
|
|
ZJ
Guest
|
|
Re: NEW PUZZLE: three locks
« Reply #7 on: Dec 23rd, 2002, 5:32am » |
Quote Modify
Remove
|
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.
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.
|
| « Last Edit: Sep 2nd, 2003, 7:56pm by Icarus » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print