问个数学问题,关于集合的.

[quote:69a10bb637="Turkish Cats"]Hoole8 的一个筒子问的:有2002位数学家参加会议,每人至少有1335位合作者,证明:可以找到4位数学家,他们中每2位都合作过.


原帖:http://www.hoolee8.com/thread-110671-1-1.html

我是这么想的,实际上是共有667种组合方式,2002个数学家选择667种组合方式,肯定有4个人是重复的...但是要怎么写证明过程啊?...[/quote]

这是图论里的一道入门题

设数学家A 有1335个合作者 (没和他合作的数学家最多也就2002-1336=666个), 而这1335个合作者中的数学家B的合作者是什么情况呢? 他发现他的合作者(也是至少1335个, A是其中的一个)中至少有1334-666=668个和A合作过. 这样我们就有了在和数学家A的合作圈内至少668个(非A非B的)数学家和数学家A与B都合作过. 下面在这和A与B都合作的668个数学家中的数学家C的情况就很明朗了: 他的至少1335合作者中, 去掉数学家A和B, 还剩1333个, 从总共1999个剩下的数学家(2002-A-B-C)里选1333个后, 只剩666个没和C合作, 这也就是说, 那AB的合作圈中(除了C外, 还有667个), 一定至少有一个数学家, D, 和C合作.

这样, A和B合作, AB都和D与C合作, 而D与C也合作, 我们发现这四个数学家互相合作. :wink: