12 3 下一页

查看: 229207|回复: 22

请客吃饭问题 [复制链接]

sokoban

银魔

Rank: 7 Rank: 7 Rank: 7

积分: 5268
帖子: 3220
精华: 19
UID: 13140
性别: 男

电梯直达

1^#

发表于 2008-10-13 11:53:12 |只看该作者 |倒序浏览

假设有 n 个人，要么互相认识，要么互相不认识。
 
现在他们轮流请客吃饭，每人请一次。
 
请饭的人把他所认识的人请来（不认识的不请），在饭桌上大家互相介绍认识。
 
所以每请一次，互相认识的人就增加了一些。
 
当他们都请过一次后，发现，还有一些人互相不认识。
 
求证：就算他们继续请客吃饭下去，那些互相不认识的人还是保持不认识。

收藏0

使用道具举报

loveddr

蓝魔

Rank: 2

积分: 406
帖子: 369
精华: 0
UID: 33926
性别: 保密

2^#

发表于 2008-10-13 11:56:24 |只看该作者

坐个沙发，明白了，懒得打字
 
设N个人为N个点，互相认识用红线连接，不认识用蓝色线。。。。。

[ 本帖最后由 loveddr 于 2008-10-13 11:59 编辑 ]

使用道具举报

金眼睛

蓝魔

Rank: 2

积分: 421
帖子: 233
精华: 2
UID: 25681
性别: 保密

3^#

发表于 2008-10-13 12:18:49 |只看该作者

没学过图论，写不出这个问题的数学描述。
 
凭感觉可以通过初始状态的相互认识情况将N个人形成连通区域，这样即使两个人互不认识，只要通过一条相互认识的链条相连，就属于一个连通区域。
 
个人观点：如果N个人形成的连通区域为M个，那么最后就将形成M个互相认识的团体。只有M=1，N个人才能相互认识。
 
N个人都请过一遍了，M个连通区域已经完全形成。

使用道具举报

lucki1987

黄魔

Rank: 3 Rank: 3

积分: 804
帖子: 584
精华: 0
UID: 34757
性别: 保密

4^#

发表于 2008-10-13 12:31:32 |只看该作者

看标题就进来了，发现误会了，，，还以为是问时间地点的呢。。。

使用道具举报

小圆来了

金魔

戴表而已

Rank: 8 Rank: 8

积分: 7446
帖子: 3421
精华: 9
UID: 45603

5^#

发表于 2008-10-13 12:42:05 |只看该作者

还以为楼主要请客吃饭

失望了

Cotton

Rank: 4

积分: 1164
帖子: 1091
精华: 0
UID: 33822
性别: 男

6^#

发表于 2008-10-13 12:42:54 |只看该作者

有点难。。。。没算出来

Best average 19.65s Best single 14.46s

使用道具举报

kexin_xiao

银魔

小欣然的爸爸

Rank: 7 Rank: 7 Rank: 7

积分: 37843
帖子: 34374
精华: 15
UID: 16477
性别: 保密

7^#

发表于 2008-10-13 12:54:14 |只看该作者

来学习了，有金眼睛在大家可以休息了，呵呵

天津1群11471969，2群5834223
3群62462688，4群62462702
5群70735234，6群33712046
7群12240584，8群29198783
9群62974165，欢迎加入！

使用道具举报

魔鱼儿

铜魔

鱼儿

Rank: 8 Rank: 8

积分: 20516
帖子: 19704
精华: 0
UID: 28712
性别: 男

8^#

发表于 2008-10-13 13:19:09 |只看该作者

呵呵呵,弄错了,我以为楼主要请谁吃饭呢?原来是这样

你即使是一条搁浅在沙滩上的鱼，也必须要学会行走。QQ:351796610已满,请加MSN:sun-shine-yu@live.cn
http://shop65338937请勿打广告com/晨曦魔方空间全场特价

使用道具举报

sokoban

银魔

Rank: 7 Rank: 7 Rank: 7

积分: 5268
帖子: 3220
精华: 19
UID: 13140
性别: 男

9^#

发表于 2008-10-13 15:13:13 |只看该作者

原帖由 金眼睛 于 2008-10-13 12:18 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=266600&ptid=15024" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A>
N个人都请过一遍了，M个连通区域已经完全形成。

关键就是要说明，为什么每人请一次，该认识都已经认识了。

使用道具举报