一家旅馆有10个房间,住有15名旅客,如果每次都恰有10名旅客同时回来.请问最少要为这15名旅客准备多少把钥匙,才能使得每次客人回来时,每名客人都能用自己分到的钥匙打开一个房间进去,并

Question

一家旅馆有10个房间,住有15名旅客,如果每次都恰有10名旅客同时回来.请问最少要为这15名旅客准备多少把钥匙,才能使得每次客人回来时,每名客人都能用自己分到的钥匙打开一个房间进去,并且避免发生两个人同时住进一个房间?

Answer 1

1#钥匙至少要有6把,如果少于6把,至少有10人没有1#钥匙,这10人回来时,无人能开1#房,不可能满足要求.
2#,3#,……,都是如此,所以至少要60把钥匙.
反之,60把钥匙够用了,可以这样分配：15个人记为A1,A2,...,A15.
1#钥匙给A1,A2,...,A6,
2#钥匙给A2,A3,...,A7,
.
10#钥匙给A10,A11...,A15,
回来的10人中标号最小的人一定有1#钥匙,标号次小的人一定有2#钥匙,……,标号最大的人一定有10#钥匙.