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. Unknown10:55 AM, December 08, 2009

    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. Pratik Poddar11:51 AM, December 08, 2009

    @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. Unknown12:06 AM, October 03, 2014

    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

Popular posts from this blog

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially)
Read more