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