0%

多人开锁问题

我也不知道这个问题原本叫什么,应该是有名字的,所以姑且就叫多人开锁问题了。

查出来了,这个东西叫门限方案,但是懒得改标题了。

$m$个人,需要任意至少$n$个人才能打开所有的锁,问最少需要多少把锁,每人最少拿多少把钥匙。

需要满足:

  1. 对任意锁,需要任意$n$个人都能打开。
  2. 对所有锁,需要至少$n$个人才能打开。

对于每一把锁,设一个长度为$m$的向量,每个元素可能的取值为${0,1}$,表示每个人是否持有这把锁的钥匙,1为持有钥匙,0为不持有钥匙。

只有当选取的$n$个元素全为0时,无法打开这把锁,所以显然当向量中0的数量小于$n$时,任意选取$n$个人都能打开这一把锁。

所以要保证任意$n$人都能打开,每把锁的钥匙数量至少为$k\ge m-n+1$。


设每把锁的钥匙数量都为$k=m-n+1$

这保证了任意一把锁,都一定能被$n$个人打开,即$n$个人一定能打开所有锁。

对于每一把锁,小于$n$人一定有至少一种情况为全0,即打不开这把锁。

如果锁包含了钥匙的所有组合,即锁的数量为$S\ge C_m^k$,这样就能够限制至少要$n$人才能打开所有的锁。

如果选取任意小于$n$人,则一定会出现至少一把锁打不开的情况。

所以要保证至少$n$人才能打开所有锁,锁的数量至少为$S\ge C_m^k$


因为$C_m^k$已经包含了锁的所有组合,再增加一把锁,它的钥匙组合一定会跟前面的重复,不能起到限制作用。

因为题目问至少多少把锁,所以可以确定锁的数量就为$S=C_m^k$


在每把锁的钥匙数量为$k=m-n+1$,锁的数量为$S=C_m^k$的情况下,一切都非常完美。

唯一的不足就是锁的数量是通过假设了每把锁的钥匙的数量都是$k=m-n+1$证明出来的,以及没有考虑每把锁的钥匙数量有没有可能不同的情况。


实现了个简单的可视化的过程,可以用于快速验证,网址链接在这里

之前我以为只适用于$m$为奇数的情况,但是其实这个适用于$m$和$n$为任意值的情况,之前只是我举例子的时候写错了,我也是写完那个小程序才发现。