钥匙分配参考答案(第三期)
修改于2019/06/14260 浏览综合
1.
题目：求50！的二进制表示中最低位1中的位置。(规定个位为第一位，以此类推)
解：二进制表示的最低位的1的位置，实际上问题可以转化为“求50！的二进制表示中末尾有几个0”，也就是统计阶乘中质因数2的个数。
参考第二期，不难得出2的个数为：
⌊50/2⌋ = 25
⌊25/2 ⌋ = 12
⌊12/2 ⌋ = 6
⌊6/2⌋ = 3
⌊3/2⌋ = 1
25+12+6+3+1 = 47
因此求1的最低位的位置即为50!中2的个数+1，即在第48位。
扩展到N！的M进制中末尾有几个0的问题，方法是通用的。
2.
题目：新办公室里有三个公用的柜子，里面放着大家可能用到的资料。每个柜子上，有一把锁和两个钥匙，小明、小赵、小王都可能随时在别人不在场的情况下打开柜子取资料。要是在不配新钥匙的情况下，如何分配钥匙，可以让他们每个人都能打开这三个柜子?
解：把一号柜子的钥匙放在二号柜子里面一把，把二号柜子里的钥匙放在三号柜子里面一把，把三号柜子里的钥匙放在一号柜子里面一把。剩下的三把钥匙每个人一把。
3.
题目：旅店有9个单人间，有10名旅客可能入住，10人中有9人同时入住，要给每人配些钥匙，使得无论哪9个人入住，总能正好入住这9个房间，且不用找别人借钥匙，问最少要配多少把钥匙？
解：
1) 每个房间至少要有2把钥匙。
否则，只有1人有这房间钥匙。假若那人恰好不来住店，那么，这个房间就不能打开。
所以钥匙数不能少于18把。
2.)每个房间有两把钥匙是足够的。
可以这样分配钥匙：
1, 2, 3, ..., 9号人分别拿一把1, 2, ..., 9号房间钥匙，第10人拿每个房间的钥匙。
这样，假如10号不住，其他人就都可住进去.
假如10号住店，1, 2, ..., 9号中就有一个不住，设他是k号。
那么，可以让除了10号的人先住他们对应号码的房间，最后让10号住进k号房间.
3)答案：最少要配18把，即每个房间两把。
4.
题目：11位科学家正在从事一项秘密工作。为了保密，大家约定：文件要锁在保险柜中，少数人无法打开保险柜，取出文件，除非人数超过了6个。问：要做到这一点，至少需要给保险柜上多少把锁？每个科学家至少要配备多少把钥匙？
解：若有题解，则至少需要462把锁，每个人需配备210片钥匙。
结论1 不能使用锁链
锁链指多把锁互相锁定，打开其中任一把锁，锁链中其它锁都失去锁定作用的策略。
证明：可使用一把锁代替锁链的作用，但是使用的锁数比锁链少，所以不能使用锁链。
结论2 每把锁至少需配5片钥匙
证明：若某把锁少于5片钥匙，则11人中至少有7人分配不到此锁钥匙，于是此7人不能开不了此锁，故取不出文件，与超过6人能打开文件的题设矛盾！
结论3 至少需使用462把锁
证明：从11人中任取6人都不能打开文件，则至少存在一把锁此6人不能打开，但剩下5人任意加入一人都能打开文件，故此5人都能打开此锁。有C(11,5)=462故知至少需要462把锁。又因每把锁至少需要5片钥匙，故每人分配钥匙数为462*5/11=210片
结论4 462把锁，每把锁5片钥匙，C(11,5)每种组合一把锁，组合中的每个人配一片此锁的钥匙，每人210片钥匙就是题解。
证明：从11人中任取7人，则能打开任意一把锁。假设某把锁不能打开，则此7人中无人有此锁钥匙，则此锁最多只有11-7=4片钥匙，与每把锁5片钥匙矛盾！从11人中任取6人，必存在一把锁，剩下5人能打开此锁，于是此6人打不开此锁，故取不到文件！