发新话题
打印【有4个人次参与评价】

[数学] 求助【九位科学家在一次国际会议上相遇,他们之中的任意三人中……】

本主题被作者加入到个人文集中

求助【九位科学家在一次国际会议上相遇,他们之中的任意三人中……】

九位科学家在一次国际会议上相遇,他们之中的任意三人中,至少有两人会说同一种语言。如果每位科学家最多会说三种,那么至少有多少位科学家能用同一种语言交谈?   (请列出解题过程,谢谢啦。)

[ 本帖最后由 kevinsun 于 2008-3-5 11:10 编辑 ].

TOP

引用:
原帖由 kevinsun 于 2008-3-5 08:11 发表 \"\"
九位科学家在一次国际会议上相遇,他们之中的任意三人中,至少有两人会说同一种语言。如果每位科学家最多会说三种,那么至少有多少位科学家能用同一种语言交谈?   (给出解题过程!)
至少应该说:“请给出解题过程。”
另外请不要用感叹号。.

TOP

估计是至少四个。

两个肯定不行,假设最多两个科学家能互相交谈。
设A、B之间能用一号语言交谈,由于假设,必须使“假设最多两个科学家能互相交谈”成立,因此没有任何第三个人会一号语言,于是剩下的七个人必须和A、B两人用别的语言交谈。根据抽屉原理,至少有四个人和A、B中的某一个人交谈,不妨设为A。而A只会其他两种语言。因此其中至少有两人能和A同时用一种语言交谈。

为什么猜4呢,因为照着上面的思路,其实只要七个人就够了,为什么放到九个?从出题心理学的角度出发,答案可能是4。剩下的继续做。.

TOP

4个的例子重新构造。echoooo帮我看看有没有错误。

1、2、3
1、5、6
1、7、8
1、7、8
5、2、8
7、2、6
5、2、7
8、6、3
5、7、3

我是检查过一遍,烦请echooooo兄再帮我查查看。
注意到第九种语言写不上去,可以猜测3个是不行的。
因为如果3个可以,那么容易知道至少需要九种语言。

[ 本帖最后由 老猫 于 2008-3-5 09:16 编辑 ].

TOP

每位科学家最多会说三种.

TOP

已经发现了,构造错误。.

TOP

一个简单的想法,科学家人数m越多,要想满足题意,会说同一种语言的人n越多。.

TOP

题目中问:至少有多少位科学家能用同一种语言交谈?
是否应改为:最多有至少多少位科学家能用同一种语言交谈?.

TOP

俺的想法是先用少一点的 m构造 n,比如3、4,找出规律。.

TOP

题目没有什么问题,你的更改繁了。.

TOP

引用:
原帖由 echooooo 于 2008-3-5 09:14 发表 \"\"
俺的想法是先用少一点的 m构造 n,比如3、4,找出规律。
你这个想法可以,可能会帮助思考。.

TOP

从集合的概念讲,实际是:
有m个集合,每个集合最多有3个不同元素,任意3个集合至少有2个同样元素。问这m个集合中,同样的元素最多至少有几个?.

TOP

现在的结论是如果至少是三个人可以交谈的话,那么就是每人会三种语言,每种语言三个人会。一共需要九种语言。.

TOP

嗯,两种讲法,完全等价。.

TOP

我找到这道题目的出处了。
是1978年的美国数学奥林匹克的题目。
但是那道题目只要证明3个,而且原证明确实用到了9个人的条件。
因此俺对出题心理学的分析出问题了。可能至少是3个。.

TOP

回复 4#老猫 的帖子

大概看了下,这比题意还严格
题目要求“任意三人中,至少有两人会说同一种语言”
现在貌似“任意三人中,会说至少同一种语言”

有5个7

[ 本帖最后由 echooooo 于 2008-3-5 10:56 编辑 ].

TOP

而且,4呢?

[ 本帖最后由 echooooo 于 2008-3-5 10:01 编辑 ].

TOP

不能构造至少3种的构造

假设可以
每个人至少可以与9-1-1=7人用同一种语言
而该人最多会3种语言,即这3种语言每种还有3-1=2次机会,
于是最多只能与2x3=6人用同一种语言
矛盾.

TOP

4种就很好构造了
123
123
145
167
246
257
346
357
456

[ 本帖最后由 echooooo 于 2008-3-5 10:27 编辑 ].

TOP

引用:
原帖由 echooooo 于 2008-3-5 10:19 发表 \"\"
不能构造至少3种的构造

假设可以
每个人至少可以与9-1-1=7人用同一种语言
而该人最多会3种语言,即这3种语言每种还有3-1=2次机会,
于是最多只能与2x3=6人用同一种语言
矛盾
不严格

假设可以
则某人a要么能与所有人同一种语言,要么不能与某一人b同一种语言

若某人a能与所有人同一种语言,
即a能与其余9-1=8人同一种语言
而a最多会3种语言,即这3种语言每种还有3-1=2次机会,
于是最多只能与2x3=6人用同一种语言
矛盾

若某人a不能与某人b同一种语言,
则b必能与其余9-1-1=7人同一种语言
而b最多会3种语言,即这3种语言每种还有3-1=2次机会,
于是最多只能与2x3=6人用同一种语言
矛盾.

TOP

引用:
原帖由 echooooo 于 2008-3-5 10:39 发表 \"\"

不严格

假设可以
则某人a要么能与所有人同一种语言,要么不能与某一人b同一种语言

若某人a能与所有人同一种语言,
即a能与其余9-1=8人同一种语言
而a最多会3种语言,即这3种语言每种还有3-1=2次机会,
于 ...
还是不严格.

TOP

回复 2#老猫 的帖子

已作更改,见谅。.

TOP

语言不通,怎么交流?.

TOP

主要证明至少三人可以讲同一语言.

把9人看成9点v1,v2,v3,v4,v5,v6,v7,v8,v9
如两人会同一种语言就在两点间联线并着染相应的颜色.
便构成一个简单图G(每三点至少有一边)
用点V1分两种情况分析:
1)点v1与其他8点都相邻,(即有连线)由抽屉原则(至多三种语言)
得至少有两边同色,不妨设为(V1,V2),(V1,V3).显而易见v1v2v3为同色
三角形.即1,2,3三人讲同一语言.
2)点V1与其他8点中至于少一点(设v2)不相邻.因每三点至少有一边.
故V3......V9发出到v1 或V2的边至少有7条,且至少有4条是连接
同一点.设此点为v1,边为(v1,v3),(v1,v4),(v1,v5),(v1,v6).  因从v1出发
至多有三色边,故上述4边必有两条同色.设为(v1,v3),(v1,v4),则
三角形v1v3v4为同色.1.3.4三人讲同种语言.
把图画一下看起来简单.就是反复用抽屉原则.

TOP

回复 24#Ted老爸 的帖子

Ted老爸,能否麻烦构造一个出来,俺都搞混了。.

TOP

.

TOP

啊,有些语言可能只有两个人会。
好构造。.

TOP

其实很简单,只要证明有一点发出两条同色线.即有存在同色三角形.
因为是证明题,要严密.只能分两种情况来讲
v1有线发出.和v1没线发出或不够线发出(必有V2有同色线发出.)
图论中通常反复设研究为第一点V1.所以看起来不太清楚.
只要同构便是同一关系,好处在于不必被很多没用的信息打扰.
echooooo的图,我看不懂.图论用点和线表示逻辑关系.G=(V,E)
点用v1,v,2,....线用e1,e2,e3....也可用(v1,v2)表示线即两点的
相邻关系.,建议你重画一下便知了(要染色),我实在不会用电脑画图..

TOP

呵呵,俺没学过图论,所以也就不知道如何表达了。

这个图是俺自创的(版权所有,不得转载 ):
每个点的括号中的数字表示每人会的语言,不同的数字表示不同的语言;
如果某两个点中有同样的数字,俺就把这两个点用线连起来,表示他们所代表的两个人会说同一种语言;
然后就凑出来了。
当然证明是没有的,属天外飞仙之类的

看来图论也是蛮好玩的,抽空学学,跟不等式比比,哪个更有趣。.

TOP

回复 26#echooooo 的帖子

我又看了你的图,点表示人.那么线表示??如是语言,则每点至多发出三条线..
题目是证明至少有三人能讲同一种语言.只要构造出一个总是存在的
同色三角形.即可.不必去考虑其他的点(人)的情况.在图论中两点间可画
两条以上线.(不一定要直线)来表示两种以上的相邻关系.如此题,e=(v1,v2),e'=(v1,v2)
e(边)表示语言,即两人会讲两种相同的语言.故通常图论证明是不会一一举例的.
说明的.这也是图论的优点
我用通俗的话讲一下:
1)如v1同V2......V9都有(8个可重复)共同语言.因V1至多会三种语言.由抽屉原则
故V1至少同两人以上会同一语言.设此两人为V2,V3,显然V1,V2,V3三人会同一语言.
2)如V1不能同V2....V9都有共同语言.假设同V2没共同语言.因为每三人至少有两人会
同一语言,故V3一定与V1或V2有至少一个共同语言.同理V4,V5,V6,V7,V8,V9也分别至少与V1,或V2
有一种共同语言.这样V3,V4,V5,V6,V7,V8,V9同V1或V2分别有七个共同语言(可能重复).
由抽屉原则,V1,V2两人中必有一人同V3,V4,V5,V6,V7,V8,V9,共同讲4个以上共同语言.(可能重复)
假设为V1.因V1至多会讲三种语言,有抽屉原则,上述4个语言必有两个是重复(为同种语言)
假设此两个重复的人为V3,V4.也即V1,V3,V4讲同一语言.
命题得证
用抽屉原则把"个"重叠为"种"是关键.当然9人也重要.否则不能用抽屉原则了

[ 本帖最后由 Ted老爸 于 2008-3-6 16:03 编辑 ].

TOP

回复 29#echooooo 的帖子

图论/组合都是离散数学的分支.主要研究逻辑关系.对计算机有很大帮助.
个人认为图论较实用,不等式要求构造一些巧妙的过度元素来证明.趣味性可能
更好些..

TOP

回复 30#Ted老爸 的帖子

谢谢Ted老爸,
图论的证明实际上与俺最初的想法是一样的,只是没想透。
后来看了你的图论解法,想通了,但好像只证明了至少要3人,但对3人是否一定能行缺乏明确的说法,于是俺就一门心思想构造一个出来,那就完整了。
事实上那个图也不完全是凑出来的,由于目标明确,就容易有想法了:
1、将这9人分为孤立的2个小组A、B,如果小组A及B里的人能两两沟通,自然就满足任意3人中至少能有2人可以沟通了;
2、2个小组的人数自然是越接近越有利,于是就分为4、5人一组;
3、接下来就是凑的做法了,由于人数不多,不是很困难。
这个做法的直接推论是10个科学家也一样。

[ 本帖最后由 echooooo 于 2008-3-6 16:42 编辑 ].

TOP

回复 31#Ted老爸 的帖子

离散数学大概是计算机专业的必修课吧?
俺是学暖通的,流体力学、热力学和传热学是必修的。.

TOP

对的,图论就是用图来帮助我们理顺各逻辑关系的.
有了图方便理解和叙述.(不然讲起来费力).
既然有兴趣.我给你一题玩一下.
有m个新生报到,发现每人都有n人不认识.现要分组:
每组三人.要求,三人全认识,或三人全不认识.
求有多少种分组.(m,n,足够大).
只要有式子有说明,不必化简..

TOP

回复 33#echooooo 的帖子

其实初中生也是可以学离散数学的.我也是初中在业余数学学校(前身)学了一些.回家
找书看一下.当时流行图论/数论题.(我不是机算机专业的),现在记得些..

TOP

回复 34#Ted老爸 的帖子

呵呵,问个问题先:
啥叫认识?
是不是相互的?
俺认识锦涛哥,可他肯定不认识俺。 .

TOP

对,认识是相互的.:.

TOP

晚上想想,理理思路也好。.

TOP

回复 38#echooooo 的帖子

把m人看作m点.如认识就连红线,不认识连黑线.
找一下有多少同色三角形,多少异色三角形.而又有
多少同色角(两条同色边的夹角).用组合记数便可
因为不用抽屉原则,所以人数随意.(不太小即可).

TOP

题目说:有m个新生报到,发现每人都有n人不认识
例如:有100个新生报到,发现每人都有98人不认识
是可以做到的,假设就是50对兄弟,不同对的都不认识。
问题是:现要分组:每组三人.要求,三人全认识,或三人全不认识,是没法做到的
因为100根本就不能被3除尽
因此,m、n必定是有限定条件的。.

TOP

题目要求出至多有多少组合乎要求.即使有人在一种分法下没有入任何组也行的.
我看到过北京小学奥数竞赛有类似题目.这题是我临时想的.因为不想你凑数再递推.
这不是线性的.目的是让你感觉一下图论对逻辑推理的帮助.
如你觉得m,n,整除3才能做,我可以改题.
再提示,同色三角形有三个同色角,而异色三角形有一个同色角(只有两色).每人可发出m-1条线
又有多少同色角???由此推出有多少同色三角形.即有多少组
切记图论只画局部图.这也是我不给你具体数字的目的.有趣吗?.

TOP

类似有m点,任三点不共线,能组成有多少三角形.

TOP

回复 41#Ted老爸 的帖子

从没做过图论的题目,所以对题型、答题要求就很陌生了。
昨天想的是:
任意2人要么认识,要么不认识
所以每个人能且只能画出m-1条线,以表示与其它m-1人的状态
有n人不认识,就画n条红线
必有m-n-1人认识,就画m-n-1条绿线
每条线都连接2人

根据题意,存在m人每人都有n人不认识,
即每人都有n条红线和m-n-1条绿线。
将这m人编号v1、v2、v3、...、vm
不失一般性,自v1考虑:
若n=m-1,则不存在2条相交的绿线,即不存在3人都认识的情况;
此时每人存在m-1>=2条绿线,不失一般性,自v1考虑:
假设v1与某人,不妨设之为v2,存在绿线;
此时v2至少还有1条绿线与他人相连,不妨不妨设之为v3;
即v1、v2、v3可以同分一组。
m人去除v1、v2、v3后继续
同理
即此m人可以分为[m/3]组。

同理,只要满足1<n<m-2,都可以。.

TOP

真的不必太复杂(图论就是帮你简化的)
每点(人)有m-n-1条绿线,n条红线
则有同色角:C(m-n-1)^2+Cn^2(任两条同色边就有一个同色角)
m人就有共:m*(C(m-n-1)^2+Cn^2)
另一方面:
设共有x个组(同色三角形)满足题意:
则有Cm^3-x个异色三角形.
上面已讲,同色三角形有三个同色角,而异色三角形有一个同色角.
共有同色角:3*x+(Cm^3-x)
得m*(C(m-n-1)^2+Cn^2)=3*x+(Cm^3-x)
解得X便可
此题还可有很多变化.但都大同小异.
Ca^b指从a中取b个有的组合.实在想不出如何用电脑表示.

TOP

回复 43#echooooo 的帖子

后来想想这是错的,因为去掉3个人就要去掉若干根线,使剩下来的人的连线变少了。
感觉图论不是以实际编出一个构造为目标,它更注重的是可能性,找出解决问题的思维和逻辑。
不过俺挺烦图论题说得太多,好像符号化程度不高。 .

TOP

回复 45#echooooo 的帖子

是的,图论和排列组合/抽屉原则都是讨论可能性和必然性.
做排列组合题也不可能用穷举吧.一般也是看局部规律来
推出全部可能,也是说的多,不会有很多符号吧.
我以为图论就是给你一种大家听的懂的话来表示你大脑想的
过程.即使不会图论也是可以思考,如同没学过方程式也能解应用题.
好了,以后有类似看来简单,但无从下手的题目,多半是
图论题.尤其美国,东欧喜欢图论题,有空看看一定有帮助..

TOP

发新话题