清华附中c1214吧 关注:218贴子:27,576
  • 10回复贴,共1

【伟大的14er】【作业】

只看楼主收藏回复

情报局
100个情报员每人掌握了一条信息, 且这些信息各不相同. 每次某情报员 A 打电话给 B ,A都将告诉 B所有他知道的, 但 B 则什么都不会告诉 A. 问: 让这些人都知道所有信息, 最少需要打多少个电话?
A) 100
B) 148
C) 150
D) 198


IP属地:北京来自iPhone客户端1楼2014-12-25 15:22回复
    这属于数学趣题吗?


    IP属地:北京来自iPhone客户端2楼2014-12-25 20:36
    收起回复
      198吧


      IP属地:广东3楼2014-12-25 20:38
      回复
        D 99个人都先打电话给一个人 这个人再打99次


        IP属地:北京4楼2014-12-25 20:39
        回复
          为什么最少?


          IP属地:北京来自iPhone客户端5楼2014-12-25 20:47
          回复
            就是如果有一个全知道了,最少一步使另一个人全知道。而是一个人全知道最少n-1步。


            IP属地:广东6楼2014-12-25 20:52
            回复
              后半句可用归纳法证,前半句可用反证法证


              IP属地:广东7楼2014-12-25 20:54
              回复
                先证后半句,若n=2,显然成立。假设n=k时需k-1步,则n=k+1时若需小于等于k-1步便可使一个人知道,k+1条情报,显然与需k-1步才可得知k条情报矛盾,所以必须要k步才可。得证。
                再证前半句,若在有且只有一个人得知全部情报时需小于等于n-2步便可使所有人得知全部情报,根据抽屉原理,必有一步使两人同时知道所有情报,与一步只可改变一个人所知道的情报不符,所以必须n-1步才可。
                综上,n人时,至少需2·(n-1)步。


                IP属地:广东8楼2014-12-25 21:12
                收起回复