※ 引述《kailoven (@#$@#^??)》之銘言： : ※ 引述《Hseuler (藍色貍貓)》之銘言： : : 在一個12個人組成的群體中 : : 任意9個人中都有5個人，他們兩兩相識 : : 請問 : : 從這12個人中，是否可以選出6個人，他們倆兩相識? : : 1)一定可以 2)不一定 3)絕對不可能 : : 謝謝 : 做完的感覺是 1 : 大概說一下我的作法 : 最簡單的"一定可以的情形"做不多說了，只要12人中的其中8人彼此都認識， : 就會在任意9人的情形下都會挑到5人彼此認識。 : 並且12人中可以找出6人彼此認識。 : 我們試著找"不可能的情形"。 : 不可能情形在10人組成的群體中還會出現， : 想像有兩個正五邊形 ABCDE 與 A'B'C'D'E' : 以下面形式做排列 : ========想像力是你的超能力========= : A B : D' : C' E' : E C : B' A' : D : ==================================== : 其中除了A A'，B B'，C C'，D D'，E E'以外，所有的邊都連上了。 : 這時候只要ABCDE五個人在一起(不論有沒有')都會互相認識， : 但沒有辦法多找到一人同時認識他們(沒有六人彼此相似)， : 此時任挑9人必定會挑進ABCDE(不論有沒有')。 : 因此如果題目是"10人群體，任意九人中有五人兩兩相識"。答案是2 : 我們接著看11人情形，由於題目是"任意九人"， : 我們只針對不合理的情況(AA'，BB'，CC'，DD'，EE'中有任一對沒被挑到) : 這種情形下沒有辦法找到5人兩兩彼此認識， : 因此第11人勢必得跟A or A'， B or B'， C or C'， D or D'，E or E' : 這些配對的人中至少其中一人認識(才能達成5人彼此認識) : 換句話說，這第11人會跟其中某個5人群體(ABCDE)也都互相認識， : 也就是6人彼此都認識。 : 所以只要大於11人群體時，我們就可以找到6個人彼此認識 : 歡迎大家一起討論啊!! : 我也不知道對不對 = =" ====補10人情形==== 感謝andan大大指導 10人情況未必如我假設.... 還是有其它情況可以滿足題目條件 我們假設上述10人情況任意少了一條邊(這邊舉例AB) 在此情況中任挑9人仍有5人彼此相識 當第11人加入時 我們還是只針對不合理的情況考慮(AA'，BB'，CC'，DD'，EE'中有任一對沒被挑到) 為了滿足5人兩兩彼此相識，但沒有6人相識 第11人勢必得跟A，B， C or C' or both， D or D or both'，E or E or both'認識 (第11人在AA'跟BB'的配對上只有AB這個配對可以選，其它的配對都會造成6人相識) 但這樣的情形會無法滿足任意挑9人中有任5人相識 (EX:CC' or DD' or EE'沒選時) 簡單來說，不管少任一條邊 第11人在避免6人相識的情形下，無法滿足任挑9人5人彼此相似的條件 而在沒有缺少邊的情況下 第11人仍無法滿足任挑9人中有5人相識時，不會有6人彼此相似 也就是說11人以上群體,任挑9人中有5人彼此相識時 就可以找到6人彼此相識 大概是這樣... 雖然自己都覺得不嚴謹 好像有一堆漏洞= = 不知道有沒有人可以推導出公式= = --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.116.245.186 ※ 編輯: kailoven 來自: 140.116.245.186 (05/18 15:30)