The chest is locked by a number of padlocks. All padlocks must be unlocked in order to open the chest. 12 Copies of the keys to the padlocks are distributed lie next to it, such that any group of 7 or more keys can open the chest should they choose to do so, but any group of less than 7 cannot. What is the minimal number of padlocks required to achieve this?

Options

A. 330
B. 495
C. 792
D. 924

Explanation

Consider the solution for a general case one where there are n padlocks and a set of k keys are able to open the padlocks. Suppose a set S of k­1 keys are trying to open the chest, there must be atleast one padlock L which will remain locked. Now get an additional key which doesn’t belong to S. This key will be able to open the last padlock L. In other words, the padlock L can be opened only if the key doesn’t belong to the set S. By the same argument, for any set of k−1 keys, there exists a lock identified by the set. Hence we must have at least (n)C(k−1) locks in total. To show that (n)C( k−1) locks are sufficient, simply biject the locks to the sets of k − 1 keys. Therefore the required answer is 12C7−1 = 924