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