Number of Locks and Keys

Problem:
7 thieves wanted to lock the treasure looted from a ship. They wanted to put locks to the treasure where each lock had multiple keys. Find the minimum number of locks N and minimum no. of keys K with every thief subject to the following conditions:-
All the locks should open each time a majority of thieves(4 or more) try to open the locks.
At least one lock remains unopened if less than 4 thieves try opening them.
All locks should have same no. of keys.
All thieves must have same no. of keys with them.

Source:
Shamir's paper on Secret Sharing Scheme states this problem and gives the answer with the explanation that its written in standard Combinatorics books

Update (11/12/09) Solution: Provided by Jaadu in comments!!

Comments

  1. number of locks required = 7C3=35.number of keys required per lock = 4.Total number keys required =140.Total number of keys each thief get = 20.
    Explanation:Let the thieves be T1,T2....,T7.suppose three thieves try to open the treasure,say T1,T2,T3.Then there must be atleast one lock that remains unopened,say L1.Now suppose one of the remaining four thief agree to open treasure,then the group of four must be able to do so.Hence,the fourth thief must have key for lock L1,and this key must be with T4,T5,T6,T7.Hence Lock L1 must have 4 keys for four thief.Now if we take any combination of three thieves we must have a lock that they are not able to open and that lock must be unique to that set of thief,for if it is not then say that set S1 and S2 of thief,both of size 3 are unable to open the lock L2,then S1 union S2 also wont be able to open the lock L2.But as size of (S1 union S2) >=4,therefore we would violate the first condition.Hence,for each set of thieve of size 3 we must have a unique lock corresponding to that set.Hence,we must have 7C3 locks.

    ReplyDelete
  2. @jaadu_max: fundoo_max... :) <3_u_max..

    Let me just generalise jaadu's explanation for N people where any K people can open the box but no K-1 people can open it.

    Let the people be T1, T2, .. TN.. Suppose K-1 people try to open.Then there must be at least one lock that remains unopened, say L1. Now suppose any new person joins the group. He must be able to open L1 as the group of K people must be able to open the box. So, all the others (N-(K-1)) should have the key to L1. So, if we take any combination of K-1 people, we must have a lock that they are not able to open and that lock has to be unique to that set, for if it is not then sat that set S1 and S2 of people, both of size K-1 are not able to open the lock L. So, S1 union S2 has size >= K and still they are not able to open the lock L, which cannot be the case. Hence, for each set of size K-1 of people, we should have at least one unique lock. So, Number of locks is at least NC(K-1).

    Also, since each set of K people should be able to open the box, at least N-K+1 people should have the keys because if not, we can get a set of K people which do not have the key to that lock :)

    So, Total number of keys per person >= Number of Locks*(N-K+1)/N that is N!(N-K+1)/N(K-1)!(N-K+1)! = (N-1)!/(K-1)!(N-K)! = (N-1)C(K-1) :)

    Fundoo max!!

    Here, since N = 7, K= 4
    Number of Locks >= 7C3 = 35
    Number of Keys per person >= 6C3 = 20 :)

    ReplyDelete
  3. N-1C k-1 corresponds to the number of distinct groups of k-1 people out of N-1 people. Now adding Nth person will make it a group of k people. Each group must be distinct. So there is a distinct lock corresponding to it. Hence Nth person must have keys of N-1Ck-1 locks.
    Do we really need 3rd and 4th conditions? Will the answer change if we remove them?

    All locks should have same no. of keys.
    All thieves must have same no. of keys with them

    ReplyDelete

Post a Comment