※ 引述《cfbbq (CF)》之銘言：
: ※ 引述《Hseuler (藍色貍貓)》之銘言：
: : 在一個12個人組成的群體中
: : 任意9個人中都有5個人，他們兩兩相識
: : 請問
: : 從這12個人中，是否可以選出6個人，他們倆兩相識?
: : 1)一定可以 2)不一定 3)絕對不可能
: : 謝謝
: 我覺得是(1)耶，以下是我的想法。
: 我先證"12人中，至少8人兩兩相識"
: pf:
: 利用反證法，假設 "12人中，最多7人兩兩相識"
: 此時，這12人中就被分成兩群 "兩兩相識(小於等於7人)"、"其他(大於等於5人)"
: 我們從 "兩兩相識" 中挑x人(x<=7)，與 "其他" 中挑y人(y>=5)，總共9人(x+y=9)，
: x+y=9 , x<=7 , y>=5 得 x<=4
: 9人中最多4人兩兩相識？與已知矛盾，所以 "12人中，至少8人兩兩相識"
: 因為 "12人中，至少8人兩兩相識" ， "所以12人中一定可以選出6個人兩兩相識" 。
: 不知道這樣子有沒有問題，有問題的話，幫我糾正，謝謝。
先直接假設相識組7人 其他組5人吧
其他組的人不能認識"所有"相識組的人，否則會出現8人兩兩相識，
但是可以認識其他組的人，也可以認識部份相識組的人。
比方 其他1 認識 相識1~相識6, 但不認識相識7, 這樣不會造成8人兩兩相識。
最簡單的例子，相識組7人兩兩相識，其他組5人兩兩相識，
相識組的人和其他組的人完全不相識，這樣最多是7人兩兩相識。
照你的取法，相識組4人+其他組5人，其他組5人就兩兩相識了，與已知無矛盾。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.175.250