珍珠湾ART

标题: A Criminal Conundrum（图） [打印本页]

作者: yunle 时间: 2004-11-3 09:17
标题: A Criminal Conundrum（图）

A set of eleven bank robbers (think Ocean’s Eleven!) decided to store their loot from a successful job in a safe (how original…) until it was safe (no pun intended…) to start spending the money. Being somewhat but not completely trustful of one another, they decided to be able to open the safe when and only when a majority of the robbers was present. Therefore, the safe was provided with a number of different locks (the key to any one not being able to open any other), and each robber was given keys to some of the locks. How many locks were required, and how many keys had to be given to any one bank robber?

前辈帮帮忙, 谢谢!

作者: hehe..... 时间: 2004-11-3 10:02
标题: 此题以前在哪里见过，挺复杂的，不过我相信这里有人能解出

此题以前在哪里见过，挺复杂的，不过我相信这里有人能解出

作者: husonghu 时间: 2004-11-3 11:11
标题: 好题。欢迎新朋友。我的答案是笨办法。不知有否好办法。

为说明方法，我从3人帮说起：

3人帮时，2人是majority，将2把锁连成一条链，锁住保险箱，共C(3,2)=3条链，
共6把锁，每人执2 key：3种不同的组合：1+2，1+3， 2+3，表示3条链中key的分布：
1表示第1人持有的key，2表示第2人持有的key，....... 这样，任何2人就能打开
保险箱。

5人帮时，3人是majority，将3把锁连成一条链，锁住保险箱，共C(5,3)=10条链，
共30把锁，每人执6 key：10种不同的组合：1+2+3，1+2+4，1+2+5， 1+3+4，1+3+5，
1+4+5，2+3+4，........ 表示10条链中key的分布：1表示第1人持有的key，2表示
第2人持有的key，........ 这样，任何3人就能打开保险箱。

同理，

11人帮时，6人是majority，将6把锁连成一条链，锁住保险箱，共C(11,6)=462条
链，共2772把锁，每人执252 key：462种不同的组合：1+2+3+4+5+6，1+2+4+5+6+7，.......
表示462条链中key的分布：1表示第1人持有的key，2表示第2人持有的key，........
这样，任何6人就能打开保险箱。

我的天 ............

等高人给出巧办法吧！锁和key的数目应大大减少才行。

作者: Solved 时间: 2004-11-3 20:38
标题: 开仓库问题的一般化

page 144

作者: hehe..... 时间: 2004-11-3 21:53
标题: 连接在此！

http://www.topchinesenews.com/viewall.aspx?topic_id=9&msg_id=878

作者: husonghu 时间: 2004-11-4 05:21
标题: 那看来我的笨办法附合独木桥的一般化。所不同的是 ----

我把原题理解为1把锁只能配1个key了；而独木桥题中的意思是每把锁可有多个key(当
然我的理解不对，至少现实中没这个必要)。所以，我的答案中的“一条链”相当于
独木桥的“一把锁”，我把“一条链”改成“一把锁”之后，就与独木桥的答案一
致了：
____________________________

3人帮时，2人是majority，共需C(3,2)=3把锁，每把锁配2个key，共6个key，每人
执2 key(当然是开2把不同锁的key)：3种不同的组合：1+2，1+3， 2+3，表示3把锁
中key的分布：1表示第1人持有的key，2表示第2人持有的key，....... 这样，任何
2人就能打开保险箱。

5人帮时，3人是majority，共需C(5,3)=10把锁，每把锁配3个key，共30个key，每
人执6 key(当然是开6把不同锁的key)：10种不同的组合：1+2+3，1+2+4，1+2+5，
1+3+4，1+3+5，1+4+5，2+3+4，........ 表示10把锁中key的分布：1表示第1人持
有的key，2表示第2人持有的key，........ 这样，任何3人就能打开保险箱。

同理，

11人帮时，6人是majority，共需C(11,6)=462把锁，每把锁配6个key，共2772个key，
每人执252 key：462种不同的组合：1+2+3+4+5+6，1+2+4+5+6+7，....... 表示462把
锁中key的分布：1表示第1人持有的key，2表示第2人持有的key，........这样，任
何6人就能打开保险箱。
_________________________________

作者: yunle 时间: 2004-11-8 06:35
标题: 回复：A Criminal Conundrum（图）

谢谢大家!

欢迎光临珍珠湾ART (http://zzwav.com/)