您当前的位置:首页 > 学习 > 阅览室

趣题:2n+1个点中任n个都与同一点相连,则存在一个连接所有点的点

时间:12-04来源:作者:点击数:

有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和所有人都是朋友。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门