魔方吧·中文魔方俱乐部

标题: 一道很简单的组合题 [打印本页]

作者: superacid 时间: 2009-6-30 14:21:34 标题: 一道很简单的组合题

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

显然题目被我篡改过了

作者: 小孩儿 时间: 2009-6-30 14:47:44

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

作者: superacid 时间: 2009-6-30 14:49:13

就是一道数学题嘛...

作者: yq_118 时间: 2009-6-30 15:58:18

好像是图论的哦

作者: r_517 时间: 2009-6-30 15:59:25

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

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

作者: superacid 时间: 2009-6-30 16:19:02 标题: 回复 5# 的帖子

......

作者: superacid 时间: 2009-7-1 08:11:18

还没做题就水了这么多

作者: lulijie 时间: 2009-7-1 18:57:34

我先把题目转化成数学语言：
一个二元函数  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 时间: 2009-7-1 19:01:00 标题: 回复 8# 的帖子

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

作者: noski 时间: 2009-7-7 01:58:15

我粗略想了一下，任意找一个人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个人，发现结论也成立。。

作者: 357433865 时间: 2009-7-7 03:47:15

反证法，我头脑中的第一反应就是！

作者: superacid 时间: 2009-7-7 07:56:01

10楼正确。11楼的约等于废话。

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)