聚会安排问题解 |
送交者: nanweishui 2005年07月23日11:04:03 于 [灵机一动] 发送悄悄话 |
Yes, we can give a pattern to this kind of problems. First, let’s generalize the problem a little bit. Suppose we have N (N>=3) friends and want to invite a triplet every night for K days. Under the restriction that each pair only appear once, we must have: C(N,2) <= K * C(3,2). The question gets interesting when the equality holds for the above equation, because in this case all pairs must appear. In your case, N = 15, K = 35 and C(N,2) = 105 = K * C(3,2). We can show that the solution exists only if N = 2^M-1 for some positive integer M>1. (I omit the proof here, but you can use the induction method using the pattern I give below). Since 15=2^4-1, we have a solution for this problem. Here is how: 1. Number each guest as 1, 2, 3, …, 2^M-1.
(xor is a bitwise operation where 0 xor 0 = 1 xor 1 = 0, and 0 xor 1 = 1 xor 0 = 1). Notice that a xor b xor c = 0 is equivalent to a xor b = c, so you can easily get the third guest if you know the other two. Also note that it is impossible that a xor b = a (or a xor b = b), because both a and b are bigger than 0. Therefore, for each pair (a, b), we can ???? a triplet that includes a and b as guests. Since there are C(N,2) such pairs, we have C(N,2) triplets. However each triplet is counted exactly 3 times because a triplet contains 3 pairs. So we get exactly C(N,2)/3 = K triplets.
|
|
|
|
实用资讯 | |