一道很简单的组合题

superacid

某个魔方聚会有3n+1个人参加，每两个人可以pk下面三种魔方中的一种：三阶、四阶、五阶。
已知每个人都与n个人pk三阶魔方，与n个人pk四阶，与n个人pk五阶。
证明：这3n+1个人中必有这样三个人，他们之间有两人pk过三阶魔方，有两人pk过四阶，有两人pk过五阶。

显然题目被我篡改过了

小孩儿

......占个沙发，没看懂楼主这个贴什么意思？

superacid

就是一道数学题嘛...

yq_118

好像是图论的哦

r_517

2楼就是来灌水的嘛= =看看今天都灌勒多少帖子了。。。

咱晚上面试回来再来想>.<今天是决定性的一天啊啊啊啊……BQ你保佑我吧- -

superacid

......

superacid

还没做题就水了这么多

lulijie

我先把题目转化成数学语言：
一个二元函数  f(x,y)  ，定义域： x、y为正整数，x<=3n+1，y<=3n+1，x不等于y。
满足 f(x,y)=f(y,x)
        f(x,y)=3或4或5
       对于任意x，   f(x,y)的值有n个等于3，n个等于4，n个等于5。
求证，必定存在三个数 a，b，c，使得  f(a,b)，f(b,c)，f(a,c) 这三个值，其中 一个值等于3，一个值等于4，一个值等于5 。

superacid

这主要是组合方面的，更精确得说是图论方面的，你把它变成代数不是自找麻烦吗？

noski

我粗略想了一下，任意找一个人A，他和N个人PK了3阶，和N个人PK了4阶，和N个人PK了5阶。
接下来只要证明：在“与A PK了3阶的N个人”中可以找到一个B，在“与A PK了4阶的N个人中”可以找到一个C，使得B和C PK过5阶。
反证一下，假设“与A PK 3阶的N个人”和“与A PK 4阶的N个人”之间，没有PK过5阶，那么这2N*N人次的5阶PK，就要分布到剩下的N+1个人之中，可是N+1个人最多PK N*(N+1) 次5阶。除非N＝1，否则N*(N+1)永远小于2N*N。矛盾。
而对于N＝1的情况，一共有4个人，发现结论也成立。。