A Criminal Conundrum（图）

yunle

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? 前辈帮帮忙, 谢谢!

www.ddhw.com

 

hehe.....

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

husonghu

为说明方法，我从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人就能打开 保险箱。www.ddhw.com 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的数目应大大减少才行。 www.ddhw.com

Solved

page 144 www.ddhw.com

hehe.....

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

husonghu

我把原题理解为1把锁只能配1个key了；而独木桥题中的意思是每把锁可有多个key(当 然我的理解不对，至少现实中没这个必要)。所以，我的答案中的“一条链”相当于 独木桥的“一把锁”，我把“一条链”改成“一把锁”之后，就与独木桥的答案一 致了： ____________________________www.ddhw.com 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人就能打开保险箱。 _________________________________www.ddhw.com

yunle

谢谢大家! www.ddhw.com