Popular computer science interview question: thieves locking treasure in cryptographic way :)

This problem is quite common in interviews with people coming from computer science background. The problem is from some famous paper on cryptography.
Problem.
7 thieves stole treasure. They would like to place N locks on it. Each lock can have several keys that can open it; a single key can open only one lock. Thieves would like to achieve the following 2 goals:
1) No 3 thieves should be able to open all locks
2) Any 4 of them should be able to open all of the locks
What is the minimum number of locks and the minimum number of keys that will allow designing such a locking system?

Solution.
To each lock there corresponds no more than one triple of thieves that can not open it. This is true because if there are more than one such triples, then we can group them and get a group of at least 4 thieves that can not open that lock. This will violate the second requirement. Therefore, the number of locks must be \ge7 \choose 3 with the minimum at 7 \choose 3 =35 locks. Now focus on any lock and the corresponding triple of thieves that can not open it. Each of the remaining 4 thieves must have a key to that lock in order for the second requirement to hold. Therefore the minimum number of keys is 4 7 \choose 3 = 140.

Advertisements
This entry was posted in Interview, Math and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s