趣题, 第8道来了。

jixch

F[6]好像可以等于8啊
1*2  3*4  5*6 结果：12   12    34   34   56   56
1*3  4*5         结果：1234    12    1234    3456    3456  56
1*6  2*4  3*5 结果：123456      123456    123456    123456    123456    123456
一共8次

jixch

F[8]好像得等于12
1*2  3*4  5*6  7*8 结果：12    12    34    34    56    56    78    78
2*3  4*5  6*7  8*1 结果：1278    1234    1234    3456    3456    5678    5678    7812
1*5  2*6  3*7  4*8
木有没有想到更少的了

jixch

另外F[5]=7,F[7]=11
不知道可不可以更少

lastwinner

tree_new_bee 发表于 2012-5-16 17:23
第5题，我的方法是靠朴素的直觉：
假设第一个蛋测试m1,m1+m2,...层，那么如果第一次蛋破后要试m1-1次， 总 ...

跟我141楼的结论一样，而且这样肯定有确定的策略

tree_new_bee

jixch 发表于 2012-5-16 21:02
另外F[5]=7,F[7]=11
不知道可不可以更少

        a        b        c        d        e
1        ab        ab                       
2                        cd        cd       
3                                cde        cde
4        abcde                                abcde
5                abcde                abcde       
6                        abcde       

lastwinner

tree_new_bee 发表于 2012-5-16 15:26
趣题6： 不同地的6个人各自知道一条不同的消息，要使每个人都知道所有消息，如果通过一对一的打电话方式，至 ...

6个人设为A、B、C、D、E、F
每通过一次电话，相当于将两个人知晓的信息结合在一起，不妨将这二人的字母结合在一起表示相互知道了对方的信息。第一个人要知道所有的信息，最少需要5次电话
A(A)<->B(B) => A(AB), B(AB) ，括号内的表示他们知晓的信息。C和D、E和F也如是，这样就是三次。
让A先知晓所有信息，A(AB)<->C(CD) => A(ABCD), C(ABCD)
A(ABCD)<->E(EF) => A(ABCDEF), E(ABCDEF)
于是，总共5次，A和E就得知了所有的信息
这时候，BCDF的状态分别是B(AB)/C(ABCD)/D(CD)/F(EF)，很显然，还是应采取之前“互补”的策略方能最快达到得知所有信息的目的。当然，当出现“信息孤岛”时，直接与已得知所有信息的人打电话，就可以一次得到所有信息了。
后续策略C(ABCD)<->F(EF) =>C(ABCDEF), F(ABCDEF)
B和D如果做互补，则互补后还各需一次通话才能得知所有消息，总共三次，所以不如他们直接与知道所有消息的人直接通话来得快，因为这样总共只需要两次。这说明，不能完全互补的两个人，需要看情况来觉得到底是互补一下再与全信息的人通话，还是直接与全信息的人通话。


所以，6个人，总共需要打5+1+2=8次电话就可以了

lastwinner

tree_new_bee 发表于 2012-5-14 07:50
恩，题出的有点模糊。
这里还是按照地面是0层来理解吧。也就是说1楼就会碎。

何止是这点模糊，万一36楼都不碎呢……这也不是不可能

newkid

lastwinner 发表于 2012-5-16 21:54
6个人设为A、B、C、D、E、F
每通过一次电话，相当于将两个人知晓的信息结合在一起，不妨将这二人的字母结 ...

思路很清晰！能够证明8最小吗？

newkid

lastwinner 发表于 2012-5-16 21:55
何止是这点模糊，万一36楼都不碎呢……这也不是不可能

36层不碎有什么问题呢？用的是同样方法。
当然37层也可能不碎，这我们就不管了。

tree_new_bee

〇〇 发表于 2012-5-16 17:00
多算一个，其实他跟第n人打电话时就有了所有消息，所以不用再打给第n人

这是一种有明确算法的做法。但不高效。
高效的做法似乎很难总结出明确的算法。

在归纳4.5.6.等等的高效做法的时候，我突然有一个想法： 假如这些知道消息的人中有些人可能会死亡，那么怎么传递消息，才能让死亡导致消息彻底丢失的几率最低呢？  
似乎解决这两个问题的做法是相同的： 让每个消息尽量早被更多的人知道， 尤其是传播少的消息更要尽早传播出去。