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

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

引用:

原帖由 kevinsun 于 2008-3-5 08:11 发表
九位科学家在一次国际会议上相遇，他们之中的任意三人中，至少有两人会说同一种语言。如果每位科学家最多会说三种，那么至少有多少位科学家能用同一种语言交谈？   （给出解题过程！）

至少应该说：“请给出解题过程。”
另外请不要用感叹号。.

估计是至少四个。

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

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

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 编辑 ].

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

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

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

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

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

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

引用:

原帖由 echooooo 于 2008-3-5 09:14 发表
俺的想法是先用少一点的 m构造 n，比如3、4，找出规律。

你这个想法可以，可能会帮助思考。.

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

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

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

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

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

有5个7

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

而且，4呢？

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

不能构造至少3种的构造

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

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

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

引用:

原帖由 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人用同一种语言
矛盾.

引用:

原帖由 echooooo 于 2008-3-5 10:39 发表

不严格

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

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

还是不严格.

已作更改，见谅。.

语言不通，怎么交流？.

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

把９人看成９点v1,v2,v3,v4,v5,v6,v7,v8,v9
如两人会同一种语言就在两点间联线并着染相应的颜色．
便构成一个简单图Ｇ（每三点至少有一边）
用点Ｖ１分两种情况分析：
1)点v1与其他8点都相邻，（即有连线）由抽屉原则（至多三种语言）
得至少有两边同色，不妨设为（V1,V2),(V1,V3).显而易见v1v2v3为同色
三角形．即１，２，３三人讲同一语言．
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为同色．１．３．４三人讲同种语言．
把图画一下看起来简单．就是反复用抽屉原则.

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

9.JPG (30.69 KB)

2008-3-6 01:29

.

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

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

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

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

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

我又看了你的图,点表示人.那么线表示??如是语言,则每点至多发出三条线..
题目是证明至少有三人能讲同一种语言.只要构造出一个总是存在的
同色三角形.即可.不必去考虑其他的点(人)的情况.在图论中两点间可画
两条以上线.(不一定要直线)来表示两种以上的相邻关系.如此题,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 编辑 ].

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

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

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

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

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

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

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

对,认识是相互的.:.

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

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

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

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

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

从没做过图论的题目，所以对题型、答题要求就很陌生了。
昨天想的是：
任意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，都可以。.

真的不必太复杂(图论就是帮你简化的)
每点(人)有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个有的组合.实在想不出如何用电脑表示.

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

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