楼主: sokoban

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

sokoban

银魔

Rank: 7 Rank: 7 Rank: 7

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

11^#

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

to 5# 8#

使用道具举报

金眼睛

蓝魔

Rank: 2

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

12^#

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

回复 7# 的帖子

欣然，听说上央视节目了啊？可喜可贺，呵呵！播出之前通知一声哦，

看看大帅哥和他的宝贝女儿，嘿嘿！

使用道具举报

金眼睛

蓝魔

Rank: 2

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

13^#

发表于 2008-10-13 20:01:51 |只看该作者

回复 9# 的帖子

如果有人答出来，LZ是不是请大家吃饭啊，<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/lol.gif" border=0 smilieid="12">
 
开玩笑了，还是谈谈我的想法吧，没有严密的数学证明，呵呵！
 
首先，对于每个连通体中的K个人，他们一定由一条相互认识的链条相连。请客的过程相当于把他们之间的关系矩阵为0的位置均变为1，最不利的情况就是他们之间只由这一条长链相连，没有其他相互认识的关系。也就是说，如果这种情况都可以通过K个人依次请客解决，其他情况就更不用说了，相当于关系矩阵中1的位置更多。 
 
对于最不利情况，—？—A—B—C—？—，假设第一个请客的是B，那么相当于ABC形成了一个小团体，BC可以通过A请客去认识左边的人，同样，AB可以通过C请客来认识右边的人，就是说，B可以从这个链条中去除。
 
这样除去K次后，K个人必定相互相识，当然总次数可以小于K。比如只有3个人的情况，B先请需1次，ACB顺序需3次。
 
这有如水银泻地，首先形成很多个小团，然后聚为一体。<IMG alt="" src="http://bbs.mf8-china.com/images/smilies/default/loveliness.gif" border=0 smilieid="28">

使用道具举报

noski

银魔

宇宙起源

Rank: 7 Rank: 7 Rank: 7

积分: 3197
帖子: 1034
精华: 12
UID: 564
性别: 男

14^#

发表于 2008-10-13 23:57:41 |只看该作者

把每个人看成一个图中的一个顶点，在请过一轮请客之后，所有连通的顶点都变成了无向完全图，即图中每两个顶点之间都有连线，也即每个人把能认识的都认识了。还没有被请到的人一定在这个图之外。。不是证明。。

The Answer to the Ultimate Question of Life, the Universe, and Everything　

使用道具举报

刚吃完

白魔

Rank: 1

积分: 109
帖子: 98
精华: 0
UID: 41408
性别: 保密

15^#

发表于 2008-10-14 01:24:52 |只看该作者

支持13，14。其实解释是相同的。

使用道具举报

sokoban

银魔

Rank: 7 Rank: 7 Rank: 7

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

16^#

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

原帖由 金眼睛 于 2008-10-13 20:01 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=267044&ptid=15024" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 如果有人答出来，LZ是不是请大家吃饭啊，   开玩笑了，还是谈谈我的想法吧，没有严密的数学证明，呵呵！   首先，对于每个连通体中的K个人，他们一定由一条相互认识的链条相连。请客的过程相当于把他们 ...

解释的很专业啊。呵呵。

使用道具举报

Cielo

透魔

有空了学学4D二阶

Rank: 6 Rank: 6

积分: 5924
帖子: 3936
精华: 0
UID: 1290
兴趣爱好: 结构
理论

17^#

发表于 2008-10-15 00:14:33 |只看该作者

原帖由 noski 于 2008-10-13 23:57 发表 <a href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=267151&ptid=15024" target="_blank"><img src="http://bbs.mf8-china.com/images/common/back.gif" alt="" border="0"></a>
把每个人看成一个图中的一个顶点，在请过一轮请客之后，所有连通的顶点都变成了无向完全图，即图中每两个顶点之间都有连线，也即每个人把能认识的都认识了。还没有被请到的人一定在这个图之外。。不是证明。。

呵呵我觉得noski所说的就是证明啊！ 开始时的每个连通分支最后会变成完全图，但两个不同的连通分支将一直处于分离状态！

使用道具举报

wangxiao148

蓝魔

Rank: 2

积分: 214
帖子: 3
精华: 0
UID: 14728
性别: 男

18^#

发表于 2008-10-17 16:55:39 |只看该作者

原帖由 Cielo 于 2008-10-15 00:14 发表 <A href="http://bbs.mf8-china.com/redirect.php?goto=findpost&pid=267899&ptid=15024" target=_blank><IMG alt="" src="http://bbs.mf8-china.com/images/common/back.gif" border=0></A> 呵呵我觉得noski所说的就是证明啊！开始时的每个连通分支最后会变成完全图，但两个不同的连通分支将一直处于分离状态！

打个比方,其中有两个人互相认识,但对其它人都不认识,那么他俩请客的时候不请其他人,其他人请客的时候也不请他俩,就永远不会认识

使用道具举报