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

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

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

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

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

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

有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次机会，
于 ...

还是不严格.

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

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

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

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

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

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

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