→ teves:我覺得這已經超出推理的範圍了,這應該去math版 05/24 21:31
推 isnoneval:這題從一開始就是圖論題啊 XD 05/24 22:23
→ teves:所以一開始就不開在這XD 05/25 17:42
※ 引述《Hseuler (藍色貍貓)》之銘言：
: 在一個12個人組成的群體中
: 任意9個人中都有5個人，他們兩兩相識
: 請問
: 從這12個人中，是否可以選出6個人，他們倆兩相識?
: 1)一定可以 2)不一定 3)絕對不可能
: 謝謝
還沒證完，不過我的想法是這樣
已知: 此12人中任取9人均可找出5人兩兩相識
假設: 此12人中無法找出6人兩兩相識
1. 從12人中取出一9人組{a1,a2,a3,a4,a5,b1,b2,b3,b4}, 令剩下3人為{c1,c2,c3}
2. 此9人組中必存在至少1組5人組兩兩相識
令此5人組為A組{a1,a2,a3,a4,a5} 其餘4人為B組{b1,b2,b3,b4}
3. A組5人中必存在至少1人不認識b1 (否則{a1,a2,a3,a4,a5,b1}就會形成6人兩兩相識)
令此人為a1
4. 同理, A組5人中必存在至少1人不認識b2
a .若b1及b2均認識a2~a5, 則b1及b2必不相識
(否則{a2,a3,a4,a5,b1,b2}會形成6人兩兩相識)
此時可表示為:
a1 a2 連線者表示"不相識"
｜＼
b1－b2
最多相識人數為 {a1,b1,b2}取1 + {a2}取1 = 2人
b. 若b1認識b2且b2認識a2~a5, 由4.a可知a2~a5必存在至少1人不認識b1,
令此人為a2
此時可表示為:
a1 a2
｜ ｜
b2 b1
最多相識人數為 {a1,b2}取1 + {a2,b1}取1 = 2人
c. 若a2~a5存在至少1人不認識b2, 令此人為a2
此時可表示為:
a1 a2
｜ ｜
b1 b2
最多相識人數為 {a1,b1}取1 + {a2,b2}取1 = 2人
其中b.及c.可視為相同(令c.之a1/a2代號互換)
5. 由4可知, 任意9人組中必存在一組4人組{a1,a2,b1,b2}，其中找不出3人兩兩相識
又a1及a2必相識，故恰有2人相識
6. 再把b3加進來, 可能的情況有以下幾種: (請自行證明)
a. a1 a2 a3 b. a1 a2 a3 c.┌a1┐ a2 a3
｜ ｜ ｜ ｜＼ ｜ b1＋b2
b1 b2 b3 b1－b2 b3 └b3┘
7. 由6可知任意9人組中必存在一組6人組{a1,a2,a3,b1,b2,b3}，其中找不出4人兩兩相識
又a1,a2,a3必兩兩相識，故恰有3人兩兩相識
==========================還沒有證但是應該沒有錯的==========================
8. 任意9人組中必存在一8人組{a1~a4,b1~b4}，其中恰有4人兩兩相識
其中必包含一6人組{a1~a3,b1~b3}，其中恰有3人兩兩相識
============================================================================
至此我們可以得到一些結論
9. {a1~a4,b1~b4,c1}必存在一組5人組兩兩相識, 此5人組必包含c1 (不見得是a1~a4,c1)
{a1~a4,b1~b4,c2}必存在一組5人組兩兩相識, 此5人組必包含c2
{a1~a4,b1~b4,c3}必存在一組5人組兩兩相識, 此5人組必包含c3
10.{a1~a3,b1~b3,c1,c2,c3}必存在一組5人組兩兩相識，包含c1,c2,c3中的至少2人
換言之{c1,c2,c3}必存在2人彼此相識
同理{a4,a5,b4,c1,c2,c3}中任取3人必存在2人彼此相識
因為打到這裡PTT就斷線了，所以就先打到這裡好了 XD
感覺再一兩個線索就要看到答案了....
假如能推出a5必定不認識c1,c2或c3，應該就QED了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.175.250