趣题, 第8道来了。

newkid · 发表于 2012-5-19 00:11

lastwinner 发表于 2012-5-18 16:07
没错，原来我还认为〇〇的方法很浪费次数，后来才发现其实也不怎么浪费次数

其实这个题要改装一下就更 ...

你也知道“双飞”之后要休息

这就变成并行任务和串行任务之间的取舍了。

newkid · 发表于 2012-5-19 00:15

lastwinner 发表于 2012-5-18 15:59
多打点字我大概能完成90%的证明，比较麻烦的有两处：
1/如何证明对于n，最少需要n－1次才能让两人知晓所 ...

第二点证明写出来看看？
假设A,B,C,D本来不是互补的，但是AB互通之后，AC, BD就变成互补的，那么总共只需3次。如果四个人分别和“全知道”的那位互通则要4次。如何证明这种也不存在？

lastwinner · 发表于 2012-5-19 00:23

newkid 发表于 2012-5-19 00:15
第二点证明写出来看看？
假设A,B,C,D本来不是互补的，但是AB互通之后，AC, BD就变成互补的，那么总共只需 ...

很模糊的写在184楼了
我将互补分为不完全互补和完全互补两种，前者在二人交换信息后，仍然处于未掌握完全信息的状态，而完全互补表示二人在交换信息后，两人都知道了所有的信息。
完全互补其实还可以细分，分为恰好完全互补和溢出完全互补，前者表示二人知晓的信息完全不一样，后者表示二人知晓的信息有重叠。但不管是恰好还是溢出，二人在交换信息后，都能知道所有的信息。

基于上述描述，我表示没看懂你第二行的疑问

lastwinner · 发表于 2012-5-19 00:44

newkid 发表于 2012-5-19 00:11
你也知道“双飞”之后要休息
这就变成并行任务和串行任务之间的取舍了。

“双飞”这个词不能随便乱用的

newkid · 发表于 2012-5-19 00:45

我只是举了一个很简单的例子。
比如ABCDE，此时E已经有了所有的ABCDE信息。其他人如下：

A:A
B:BE
C:CD
D:CD

AB先通一下，变成：
A:ABE
B:ABE
C:CD
D:CD

此时就形成AC互补，BD互补。剩下再两次，总共三次，ABCD就拥有了全部信息。

如果A,B,C,D分别和E通话，则需要四次。

lastwinner · 发表于 2012-5-19 00:49

本帖最后由 lastwinner 于 2012-5-19 00:51 编辑

newkid 发表于 2012-5-19 00:45
我只是举了一个很简单的例子。
比如ABCDE，此时E已经有了所有的ABCDE信息。其他人如下：

事实上你这个例子是不合理的，因为E：ABCDE，所以ABCD四个人中，至少应该有一个人知道E消息，A也不可能只知道自己的消息，而每个人目前知晓的信息都不超过2个，所以至少应该有两个人都知道E消息，E才可能知道所有的消息

newkid · 发表于 2012-5-19 00:53

lastwinner 发表于 2012-5-19 00:49
事实上你这个例子是不合理的，因为E：ABCDE，所以ABCD四个人中，至少应该有一个人知道E消息，A也不可能只 ...

当然不合理啦，我也造不出反例，只是举了一个极端例子，说明即使目前没有互补，经过某些交换后会形成互补而且比逐个通话要好。

lastwinner · 发表于 2012-5-19 01:21

newkid 发表于 2012-5-19 00:53
当然不合理啦，我也造不出反例，只是举了一个极端例子，说明即使目前没有互补，经过某些交换后会形成互补 ...

从逻辑的角度上讲，不可能的例子举出来是没用的

假设有n人，其中两人已经知晓了所有的信息，而其他的两两之间的信息都不能通过一次通话就达到完全互补的状态，那么一个人最少需要通过两次通话才能达到完全互补。这个人在两次通话后，除了他还会有第二个与他通话的人知晓了所有的信息………………

写不下去了，缺乏一些前提，会落入到类似你写的不合理例子的漩涡中，又没法反驳