※ 引述《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