有锁若干把,现在有六个人各掌握一部分钥匙,已知任意两人同时去开锁有且恰有一把打不开,而任何三个人都可以把全部锁打开,问最少有多少把锁?

Question

有锁若干把,现在有六个人各掌握一部分钥匙,已知任意两人同时去开锁有且恰有一把打不开,而任何三个人都可以把全部锁打开,问最少有多少把锁?

Answer 1

假设一共有n把锁,构造S={1,2,...,n}
令6个人持有的钥匙组成集Bi⊂S.于是对任意不同的i,j,k有：
|Bi∪Bj|=n-1
|Bi∪Bj∪Bk|=n
明显,对任意不同的i,j,k,m,Bi∪Bj≠Bk∪Bm,否则|Bi∪Bj∪Bk|=n-1.
于是n≥C(6,2)=15
假设B1∪B2=S-{k},那么必然k∈B3,B4,B5,B6.否则不满足|Bi∪Bj∪Bk|=n
同理,对任意k∈S,都有且只有4个Bi包含k.因此|Bi|=15*4/6=10
B1={1,2,3,4,5,6,7,8,9,10}
B2={1,2,3,4,5,6,11,12,13,14}
B3={1,2,3,7,8,9,11,12,13,15}
B4={1,4,6,7,9,10,12,13,14,15}
B5={2,5,6,8,9,10,11,13,14,15}
B6={3,4,5,7,8,10,11,12,14,15}