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