設萬維讀者為首頁 廣告服務 技術服務 聯繫我們 關於萬維
簡體 繁體 手機版
分類廣告
版主:
萬維讀者網 > 靈機一動 > 帖子
聚會安排問題解
送交者: 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 | 全球最佳航空公司出爐:海航獲五星
海外華人福利!在線看陳建斌《三叉戟》熱血歸回 豪情築夢 高清免費看 無地區限制
一周點擊熱帖 更多>>
一周回復熱帖