Quod Erat Demonstrandum

2008/07/13

組合小談

Filed under: Additional / Applied Mathematics,HKALE,Pure Mathematics — johnmayhk @ 2:11 下午
Tags:

某班有 30 名學生進行互訪,每個學生在一個晚上可以進行多次出訪。但在客人來訪的晚上,他必須留在家中。
證明:為了使每個學生都訪問了他的每一位同學,七個晚上已經足夠。

這道是 1986 年中國隊的 IMO 訓練題。

但這絕對可以變成數學的『生活應用題』。嗯,比方話…已往 HKU 某些 hall 喜歡有所謂『洗樓』活動,即是要新丁叩門入房認識全 hall 的人。考慮成本效益,當然不能『晚晚係咁玩』;那麼最少要多少晚才可以完成『洗樓』呢?諸如此類,其實(再吹大一些)都和分配物資等物流上的考慮有關,牽涉數學上有一門稱為『組合學』的學問。

說回上題,給一個精煉的建議解答:

設七晚為 {1,2,3,4,5,6,7},取三元(elements),共得 _7C_3 = 35 個三元子集。在那些三元集中任取 30 個,名之曰 A_i 。設A_i = {第 i 個學生留在家中的晚上},那麼對於任意 i, j (i \ne j),存在 k \in A_i \ A_j,只要命第 j 個學生於第 k 個晚上探訪第 i 個學生便可。

我附加的多餘話:上面的分配方法是,每個學生有 3 晚留在家中,其餘 4 晚出動探人。所謂 A_i \ A_j,用 OL (ordinary language) 即是說:學生 i 留在家而學生 j 出動的晚上。因為 A_i 各不相同,明顯地 A_i \ A_j 非空,即是肯定有一晚是學生 i 留在家而學生 j 出動的晚上,那麼就安排那個晚上讓學生 j 探望學生 i 吧。就是很簡單的道理,正如那天聽岑教授說:數學比賽的題目,拆穿條『橋』就『唔值錢』了。

如果做下無聊的 SBA,可以給同學一堆 30 個具體的人名,著同學編個『探訪時間表』給我,甚至把這個虛擬的習題付諸實際行動云云。

不少關於三元集的題,在單墫教授的舊作《集合及其子集》的小書中,有以下例子:

求所有自然數數對 (m,n),使得集 X = {1,2,3,...,n} 有 m 個三元集 A_1, A_2, ..., A_m 滿足:
(i) X 的每一對元素(即二元子集)恰巧在一個 A_i (1 \le i \le m) 中;
(ii) A_1, A_2, ..., A_m 中每兩個恰巧有一個公共元。

經由短短的證明,只可能存在兩個數對,分別是 (1,3) 及 (7,7) 滿足題意,大家不妨試試。其中 (7,7) 的情況,以圖示之頗為漂亮,見下:

書中提及 (7,7) 的情況就是組合學中著名的『有限射影平面』,圖為把三元子集作為『直線』的情況,只是無法在歐氏平面顯示『直線』{2,4,6}。(注:單教授另著的《組合幾何》亦是非常有趣的書,大家找找看。)

說到這裡,下次希望介紹組合學中一個有趣的定理:結婚定理

題外貼圖:

明報這幅真有趣,iphone 熱燒到出家人那裡?!但最抵死係,在某『粥谷』把上圖配以標題:『我不入 iphone,誰入 iphone』…

3 則迴響 »

  1. This question is weird.. what about this? Did I misunderstand something?
    Label the students as 1,2,…,30
    On the first night, 16-30 stay at home, 1,2,3,…,15 visit everyone of 16-30.
    After this night, each one of {1,2,..,15} and {16,..,30} have visited each other.
    We use similar method for the two disjoint subsets {1,2,..,15} and {16,…,30} now. e.g. 8-15, 23-30 stays at home, 1-7 visit 8-15, 16-22 visit 23-30.
    Repeat. In this way, students will visit 15 ppl on the first day, 8 ppl on the second, 4 on the third, 2 on the fourth. After 4 days they would have visited all other 29 students.

    迴響 由 Soarer — 2008/07/15 @ 4:54 下午 | 回覆

  2. 謝謝 Soarer。原題指的互訪,是 A 到 B 的(比方說)宿舍探訪後,B 也要往 A 宿舍探訪他。但 Soarer 指出的更合符現實。

    迴響 由 johnmayhk — 2008/07/15 @ 8:00 下午 | 回覆

  3. “是 A 到 B 的(比方說)宿舍探訪後,B 也要往 A 宿舍探訪他"

    I see, no wonder I found “7 nights" weird.

    迴響 由 Soarer — 2008/07/17 @ 1:31 上午 | 回覆


RSS feed for comments on this post. TrackBack URI

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 變更 )

Twitter picture

You are commenting using your Twitter account. Log Out / 變更 )

Facebook照片

You are commenting using your Facebook account. Log Out / 變更 )

Google+ photo

You are commenting using your Google+ account. Log Out / 變更 )

連結到 %s

在WordPress.com寫網誌.

%d 位部落客按了讚: