设万维读者为首页 广告服务 技术服务 联系我们 关于万维
简体 繁体 手机版
分类广告
版主:
万维读者网 > 灵机一动 > 帖子
聚会安排问题解
送交者: 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.
2. Get the M-bit binary expression for each number
3. If three numbers a, b, and c satisfy a xor b xor c = 0, group these guests as a triplet.

(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.

0%(0)
0%(0)
标 题 (必选项):
内 容 (选填项):
实用资讯
回国机票$360起 | 商务舱省$200 | 全球最佳航空公司出炉:海航获五星
海外华人福利!在线看陈建斌《三叉戟》热血归回 豪情筑梦 高清免费看 无地区限制
一周点击热帖 更多>>
一周回复热帖