端脑吧 关注:37,708贴子:687,662

回复:【终极头脑风暴】——【神之裁员】——你能闯入第几层?

只看楼主收藏回复

有1001个号码,每个人可以知道其中的999个号码。不知道的2个号码一个是老板藏起来的,再就是自己的。
如此,只需要报这个两个号码中的一个就好了。
在此情况下,假设第一个人就报错,没问题,那第一个人报出的号码就是老板手中的号码了。后面的人就都知道自己的号码是多少了。
如果第一个人报对了,后面的人的情况还是一样的。如此循环,最好的情况是1000个人全部可以被保留下来


IP属地:湖北121楼2014-12-12 14:13
收起回复
    本人看了动画第二集后才来关注端脑吧(今天刚来的新人一枚),刚刚发现这个帖子,觉得这个题目挺有意思的。
    由于这里是端脑吧,我就尝试通过逻辑推理的方式来解决第五层的问题。(首先声明,本人从未看过原题解法,如有雷同,纯属巧合。)
    首先,从题目可知,有2个隐藏的条件:
    1、任何一个人都能听到后面所有人报的数,否则信息无法传递,题目就失去了意义了。
    2、当一个人报出数字后老板不会立即告诉其他人是否正确,否则同样题目会失去意义。
    当然了,我看了下回复,什么通过不同的描述方式传暗号这样的手段就更不允许了。
    作为最后1个人,无论如何都只有50%的胜率,因此如果要只牺牲一个人,那就必须是他。
    假设最后一个人不知道的两个数字分别为A、B,为了使其他人都能正确,于是他能报的数字只能是二者之一,不能报其他数字。
    假设他报了一个数字A,并且假设在他之前的人,都能报正确的数。那么在更前面的人面临的问题就变为:在自己头上的数字与B之间做出选择。
    于是,所有人都只需要进行2选1就行了。
    那么,每一个人所能知道的所有信息是什么呢?
    1、他能看到前面每一个人头上的数字。
    2、他能听到后面每一个人报出的数字。
    于是他就能把所有数字(包括他自己的未知数X和最后一人报出的数字A)按顺序排列变成一个1000维的向量。
    这个向量就包含他知道的全部信息。
    从这里可以看出结论1:除了最后一人外,其他人从本质上来说都是无法向前面的人传递信息的。
    的确,每一个人都能给前面的人报出自己的数字,帮助前面的人排除一个错误答案。但对于前面的人来说,这跟从一开始就直接看到他头上的数字是没有区别的。
    由此,在假设只牺牲最后一人的假设条件下,原题目等价于:
    前999人每一个人都能看到除了自己以外的剩余998个人头上的数字,最后一个人能看到除了自己外的前999人的数字……(题目后面的内容相同)
    于是,最后一个人为了将信息传递给前面999人中的每一个人,他必须以某种方式将前面999个人的数字的信息都通过某种方式包含在他报出的数A中(必须包括所有999个人的数字信息,不能少任意1个人)。
    现在假设,这种方式与前999个数字的排序无关,因为总共只有1001个数,所以只要知道剩下的两个数A和B是什么就能立即知道其余999个数分别是什么了。
    原题将等价为:给你1-1001中的任意两个数A和B,你能否只说出A,其他人就立即知道B是什么?
    显然,这是不可能的。
    于是,证明了这种传递信息的方式必然与前999个数字的排列顺序相关。(也就是说想通过奇偶性或者求和、求余这些方式来解决问题是不可能的。)
    但要用简单的A或者B两个选择就给出999个数字排列顺序的信息,我唯一能想到的就是逆序数的奇偶性了。
    于是我很容易地就给出了第五层的解决方法:
    将老板看着第1001个人,第1000名员工不知道自己和老板的数字究竟谁是A谁是B,但必然有A大于B或A小于B。
    第1000名员工只需要报出A、B中的一个数字,把另一个数字留给老板,使得所有1001个数字排列的逆序数为奇数或者偶数(事先跟其他员工约定好了奇偶)就行了。


    123楼2014-12-14 23:43
    收起回复
      这个其实只有三中情况。我们假设第一个,第二个,第三个报数的分别为甲,乙。丙。
      第一个报数的唯一不知道的是自己和老板的数字。
      我们假设为a1和a2。甲面临两难。知道乙的数字。
      这里我们再分。第一种情况。无论用和也好,用其他方法也好。那么使乙知道了自己的数字。甲一定被淘汰。
      乙面临两难的选择。报自己的数字保证自己不被裁掉和不报自己的数字,给丙提示。假设他报自己的数字。那么丙讲面临和甲一样的境地。他只知道乙和其他员工的数字。不知道自己与甲还有老板的数字。如此循环。至少保证一半存活。
      如果乙用方法让丙知道了自己的数字。那么乙被裁掉。那么丙有面临和乙同样的境地。如此循环,全部裁掉。
      另外一种。还是回到甲。甲不给乙提示。直接懵。a1a2任选一个。假设甲蒙对了。甲不被裁掉。那么乙还是不知道自己的和老板的。他也只能蒙。如此循环。五五开。


      来自手机贴吧125楼2014-12-16 08:40
      收起回复
        我就想知道第二个人报出自己的号码的时候,第三个人根据什么算出自己的号码?前面的人只能报自己的,不能再给任何提示,脑残吧,还特么有一帮脑残在这讨论这个问题,你们怎么不想想从很高很高的天空掉下来水会不会砸死人呢。脑袋都没长完全 还算数学题呢 我也是醉了~!


        126楼2014-12-17 13:46
        收起回复
          和我来一起膜拜楼上的大神们啊@榴莲塞菊花擦疼 @彩虹仰望天空


          来自Android客户端128楼2014-12-17 21:07
          收起回复
            这个纵队的规格怎么说。 不知道这个纵队横列数目。 要是1*1000那就好猜了


            IP属地:山东129楼2014-12-18 13:20
            收起回复
              看题目好像是随机一路纵路就行吧?那就只排一条纵队,每个人由后面一个人告诉他号码,至于最后一个人去蒙了2选1,至少也能999了。


              131楼2014-12-18 19:40
              收起回复
                最后一人将前方数字以行列式排列,若为偶排列,则报大,若为奇排列,则报小


                IP属地:陕西132楼2014-12-19 06:04
                收起回复
                  有必要分析的那么复杂吗?先假设有可能保留住999人,那么这999人一定报的都是自己的号码,仅有一个人被淘汰,那么被淘汰这个人显然就是最后一个人,那么他只需要报出前面999个人的数字和即可,第999个人,用第1000个人报的数减去前面所有人的和,报出自己的号码,第998人用第1000人的数减去999人的号码和前面的总和得出自己的数,报出自己的号码,依次类推所有人都可以报出自己的号码。是我想的太简答了吗?


                  IP属地:山东133楼2014-12-19 11:58
                  收起回复
                    我只想说推理吧中很早就有这题目了不过那里是国王和一千个智者


                    IP属地:安徽来自手机贴吧134楼2014-12-19 13:53
                    收起回复
                      猜个蛋,末数报排前面一个号码就可以,这么简单的问题复杂化


                      来自手机贴吧135楼2014-12-19 14:05
                      回复
                        猜个蛋,末数报排前面一个号码就可以,这么简单的问题复杂化


                        来自手机贴吧136楼2014-12-19 14:06
                        收起回复
                          我最讨厌用十五个字来水经验的。


                          IP属地:广东来自Android客户端137楼2014-12-20 16:48
                          回复
                            70楼有答案想要看的可以去看下


                            138楼2014-12-20 22:21
                            回复
                              从来不回贴的我来回一帖
                              每一个员工都能看到队伍里排在自己前面的所有员工的号码牌
                              最后一个员工可以看到前面所有员工的号码,只是不知道自己,跟老板的,他只是2选一,比如,他只看不到998跟999他如果猜998那么他就错了,那么,所有员工就知道老板的号码是998,那么倒数第二个员工看不到的号码就是998、999跟一个他自己的数字,他已知老板是998 他就报出除老板与第一个淘汰员工的数字


                              来自手机贴吧139楼2014-12-21 01:06
                              收起回复