相识问题一例，欢迎帮助

zijingdijiu · 发表于 2004-3-4 01:52:03

[B]我们这有一个问题：9个人中一定有3个人互相认识或者有4个人互相不认识。要证明这个问题，百思不得其解，希望高手指点。据了解用图论的相关只是可以解决，请求帮助[/B]

knight · 发表于 2004-3-4 03:31:51

抽屉原理

math618 · 发表于 2004-3-4 20:41:55

大概是这样吧：
用9个点表示9个人，互相认识的连一条边。
含9个点的完全图有36条边，若“有4个人互相不认识”不成立，则此图至少有x条边。当一个含9个点的图有x条边时，它一定有一个只含3个点的圈。
由于图论都忘得差不多了，不知道上述思路是否正确，好象有点多余。

zijingdijiu · 发表于 2004-3-6 01:48:14

感谢你对相识问题的回复，那么你可以具体点讲吗，想不出来啊
[move]谢谢帮忙！[/move]

heyi · 发表于 2004-3-6 17:20:07

你可以把9个人在图上表示为9个点，用红线和蓝线连接任意两个点分别表示两人相识或不识。然后你就会发现你所要的答案。
这个问题在初中的竞赛中就有，不过对于没有见过的人来说还是比较麻烦的。

zijingdijiu · 发表于 2004-3-6 20:39:13

问题好像不是那么解决的，我们当然可以看出那个结论，
可问题是，我们怎么才能证明，你作图只是若干种情况，怎么才能覆盖全呢？
麻烦了，具体说明[SHADOW=255,blue,1]具体说明

heyi · 发表于 2004-3-8 17:31:44

knigh 说的就是原理，我只是形象的说明。这个问题原先我见过的是很多人通信（比如现在可以用2004个人通信），你想想如何用抽屉原理来选择线段和点就行了。

lex · 发表于 2004-3-11 22:08:02

你的相识包不包括　A认识B而B不认识A　的情况啊

yizi00002000 · 发表于 2004-4-13 05:09:00

建议看一下清华出版的<<组合数学>>,好象有个类似的例题,讲的够详细,明白.

math618 · 发表于 2004-4-14 01:34:16

还没搞定？
首先，相识不包括“A认识B而B不认识A”的情况。
然后，用图表示这9人的关系——认识的连一条边，构造图G=(V,E)。
现在证明此图中或含完全图K3，或含4阶零图N4。
对于任意V中一点x，……
还是找一本组合数学的书看看，其中的Ramsey定理。

http://www.shumo.org/bbs/dispbbs.asp?boardID=108&ID=4025&star=4

[此贴子已经被作者于2004-4-21 6:27:37编辑过]

		自动登录	找回密码
密码			注-册-帐-号