The fewest number of keys for the bank.

tcpip004

A president of a bank wants to put some locks on the door to the vault.  He has two Directors and five Managers.   Each lock has a different key, and multiple copies can be given out to different people.  All locks must be opened to open the door.  He would like:

 

1.  To be able to open the door by himselfwww.ddhw.com

2.  Both Directors can open the door if together (but not one director)

3.  Any director with any two Managers can open the door (but not one manager)

4.  Any four Managers can open the door  (but not three managers)

 

What is the fewest number of locks needed, and how are the keys distributed?

www.ddhw.com

 

独木桥

至少需要20把锁. 钥匙分配如下: L1:P,D1,D2,M1,M2www.ddhw.com L2:P,D1,D2,M1,M3 L3:P,D1,D2,M1,M4 L4:P,D1,D2,M1,M5 L5:P,D1,D2,M2,M3 L6:P,D1,D2,M2,M4 L7:P,D1,D2,M2,M5 L8:P,D1,D2,M3,M4 L9:P,D1,D2,M3,M5 L10:P,D1,D2,M4,M5 L11:P,D1,M1,M2,M3,M4 L12:P,D1,M1,M2,M3,M5 L13:P,D1,M1,M2,M4,M5 L14:P,D1,M1,M3,M4,M5 L15:P,D1,M2,M3,M4,M5 L16:P,D2,M1,M2,M3,M4 L17:P,D2,M1,M2,M3,M5www.ddhw.com L18:P,D2,M1,M2,M5,M5 L19:P,D2,M1,M3,M4,M5 L20:P,D2,M2,M3,M4,M5 （转自：顶顶华闻 www.TopChineseNews.com ） 少于20把锁是不可能的.理由如下: 有10个人3Manager组合,每个3Manager组合,至少有1把锁不能开; 有10个人1Ditector+1Manager组合,每个组合至少有1把锁不能开; 以上20个组合中,任意两个不同的组合合在一起(两个不同的组合可以 有部分相同成员)都能开门,所以20个组合对应的不能开的锁是不同的. 因此至少需要20把锁. www.ddhw.com

aaa

i.e. How can you unlick L1 with D1, M3 and M4? www.ddhw.com

fzy

20 locks   L1: P, D1, D2, M1, M2 L2: P, D1, D2, M1, M3 L3: P, D1, D2, M1, M4 L4: P, D1, D2, M1, M5 L5: P, D1, D2, M2, M3 L6: P, D1, D2, M2, M4 L7: P, D1, D2, M2, M5 L8: P, D1, D2, M3, M4 L9: P, D1, D2, M3, M5 L10: P, D1, D2, M4, M5 L11: P, D1, M1, M2, M3, M4www.ddhw.com L12: P, D2, M1, M2, M3, M4 L13: P, D1, M1, M2, M3, M5 L14: P, D2, M1, M2, M3, M5 L15: P, D1, M1, M2, M4, M5 L16: P, D2, M1, M2, M4, M5 L17: P, D1, M1, M3, M4, M5 L18: P, D2, M1, M3, M4, M5 L19: P, D1, M2, M3, M4, M5 L20: P, D2, M2, M3, M4, M5 www.ddhw.com