Re: 相識 - 推理遊戲

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

--