主题：如何分摊秘密（一）——从《鹿鼎记》中的四十二章经说起 -- 明日枯荷包

multiple证明的是, 为了保证任意m个人在场时能开门, 而任意m-1个人都不能开门, 那么至少需要C(m-1,n)个锁, 每个锁至少需要n-m+1把钥匙.

接下来可以证明, C(m-1,n)和n-m+1作为下界是可以达到的. 即存在一种钥匙分配方式, n个人中的每一个都分配C(m-1,n-1)把钥匙, 使得任意m个人在场时能开门, 而任意m-1个人都不能开门. 注意C(m-1,n)*(n-m+1) = C(m-1,n-1)*n = C(m,n)*m.

这个证明应该不难, 但也不直观. 具体到n=5,m=3的情况时, 可给出以下的分配方案: {1,2,3,4,5,6}, {4,5,6,7,8,9}, {1,2,4,7,8,10}, {2,3,5,8,9,10}, {1,3,6,7,9,10}. 不难验证, 此方案可以保证任意3个人能开门, 而任意2个人不能开门.

关于存在性的一般证明, 我想任意m-1个人应该恰好拥有n-m+1把共同钥匙, 同时他们的合集应该恰好缺少1把钥匙.