魔方吧·中文魔方俱乐部

标题: 请客吃饭问题 [打印本页]

作者: sokoban 时间: 2008-10-13 11:53:12 标题: 请客吃饭问题

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

作者: loveddr 时间: 2008-10-13 11:56:24

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

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

作者: 金眼睛 时间: 2008-10-13 12:18:49

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

作者: lucki1987 时间: 2008-10-13 12:31:32

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

作者: 小圆来了 时间: 2008-10-13 12:42:05

还以为楼主要请客吃饭

失望了

作者: 檰誮餹 时间: 2008-10-13 12:42:54

有点难。。。。没算出来

作者: kexin_xiao 时间: 2008-10-13 12:54:14

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

作者: 魔鱼儿 时间: 2008-10-13 13:19:09

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

作者: sokoban 时间: 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个连通区域已经完全形成。

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

作者: Wukiy 时间: 2008-10-13 15:13:47

有点难....没有完全搞懂....

这样是无限循环呀

作者: sokoban 时间: 2008-10-13 15:14:14

to 5# 8#

作者: 金眼睛 时间: 2008-10-13 19:31:03 标题: 回复 7# 的帖子

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

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

作者: 金眼睛 时间: 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 时间: 2008-10-13 23:57:41

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

作者: 刚吃完 时间: 2008-10-14 01:24:52

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

作者: sokoban 时间: 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 时间: 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 时间: 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所说的就是证明啊！开始时的每个连通分支最后会变成完全图，但两个不同的连通分支将一直处于分离状态！

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

作者: kexin_xiao 时间: 2008-10-17 20:40:21 标题: 回复 12# 的帖子

地球人都知道了啊

作者: kexin_xiao 时间: 2008-10-17 20:41:09

看了13\14楼的解释,学习了

作者: 小圆来了 时间: 2008-10-17 23:08:55

我这人比较好吃

学习了

谢谢楼主

这样的帖子最容易吸引我

作者: ggglgq 时间: 2008-10-21 21:02:51

            金眼睛、noski 等人的理解和解释都比较通俗易懂！不错！           本人联系魔方说明一下。比如正六面体三阶魔方，N 个块都按楼主的“请客方法”   转过一遍后，M 个颜色“团体”就形成了！  别忘了还有“几何中心块”是一个“单个体”   的“团体”喽！呵呵！     <applet code="RubikPlayer.class" codebase=3 width="300" height="300">
 <param name="scrptLanguage" value="SupersetENG">
 <param name="stickersFront" value="3,4,3,4,5,4,3,4,3">
 <param name="stickersRight" value="3,4,3,4,5,4,3,4,3">
 <param name="stickersDown" value="3,4,3,4,5,4,3,4,3">
 <param name="stickersBack" value="3,4,3,4,5,4,3,4,3">
 <param name="stickersLeft" value="3,4,3,4,5,4,3,4,3">
 <param name="stickersUp" value="3,4,3,4,5,4,3,4,3">
</applet>                 其他  正 A 面体 B 阶魔方的颜色“团体”实例大家自己思考吧！            

[ 本帖最后由 ggglgq 于 2008-10-21 21:10 编辑 ]

作者: qq350616494 时间: 2008-11-16 14:39:36

楼主，你请我们吃饭，MONEY你出，试下不就知道了吗~

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)