2008-09-07 3:41| 
9 Comments | 本文内容遵从有2n+1个人，他们的朋友关系满足这样一种奇特的性质：任选n个人，则在剩下的人中总能找到一个人，他和这n个人都是朋友。求证，存在这样一个人，他和所有人都是朋友。我们假设朋友关系是双向的，也就是说如果A是B的朋友，那么B一定是A的朋友。
这明显可以转化为一个图论问题。选出两个互为朋友的人。我们得到了一个大小为2的团（一个“团”就是一个所有结点两两相连的子图，或者干脆说是完全图形状的子图）。和另外n-2个人并在一起，则存在一个人和他们都是朋友（当然和那两个人也就是朋友了）。把这个人加进刚才那个团里，于是我们得到了一个大小为3的团。又随便取n-3个人和这3个并在一起，则有一个人和所有这些人都是朋友，于是我们继续扩展出一个大小为4的团。反复进行这个操作，直到我们得到一个大小为n+1的团，此时团的大小已经不能再继续扩展了。但是，一旦注意到此时不属于团的人只剩n个了时，我们发现问题已经解决了：在团里面存在一个人P，他和不属于这个团的那n个人都是朋友。而P本身在一个大小为n+1的团里面，他和团里的其余n个人都是朋友。因此，P和所有人都是朋友。
来源：http://www.cut-the-knot.org/arithmetic/combinatorics/Clique.shtml
抢个小沙发～～～～我还没睡～～～
强！！！
我也不会说别的了
强！！
嗯，赞~
嗯，强~~~~
嗯，妙
我沒有看懂 能不能解釋一下呢
回地壳：
n+1组是选择出来的，里边都互相是朋友；
剩下的n个人是题目给出的条件 -- 任意n的人的一群，从剩余的人种（n+1那群）有一个和他们全是朋友。
于是证明了。
我来构造楼上的n+1人组吧。
任意选择n个人，则根据条件，在剩下的人中，有一个人认识这里面所有的人。然后将这个人补充进n个人中，再从n个人中任意去掉一个，重新构造一个n人组，则剩下的人中一定有一个人认知这n个人，再把这个人纳入进来，再随机去掉一个。如此循环，每次新增一个认识其他所有人的人进来，在随机去掉一个原始n人组中的人，循环到第n次的时候，可知其中n个人互相都认识，这时外面的人中一定有一个人认识这全部的n个人，这样，就形成了一个全部互相认识的n+1人组。
最后，还剩下的n个人组成一个组，则在相互认识的n+1人组中，一定有1个人认识n人组的所有人，则这个人一定认识除自己以外的所有2n个人。