端脑吧 关注:37,739贴子:687,738

【神之裁员】——第五层答案参考

只看楼主收藏回复

贴出答案之前我先要说几句:
首先,这答案是我自己一个字一个字码出来的,我不是啥专业研究的人,只是一个普通高中生而已,写出来是为了尽量让大家看的明白,而不是为了用各种专业术语引来一坨“不明觉厉”。所以,你如果觉得我的语言有点滑稽有点不专业那是很正常。这道题【第五层】个人认为是用来考验“构造”、“逻辑完整性”与“逻辑严密性”,而不是考验专业程度和知识文化程度的。
当然这不一定是唯一答案,虽然即使有其他答案,至多是第一个人所报的数的特征不同。
原帖中很多人都下意识的想出了“平均数”这个办法,但是还是太小看这道题目了,如此单纯的想法不能严密解决问题,不能保证“报出1-1001之间不重复的整数”,而且这个类型的方法也至多达到【第四层】(不是瞎说哦,逻辑证明得出来的哦)。当然【第四层】其实和【第五层】相差的非常非常之多,用我一同学的说法就是“第一个报数的人同样是跪,却是以一种非常神奇的方式跪掉的”。
好了接下来是答案公布:
首先是两个自定义概念与一个引理,接下来要用:
①.情况的“对应排列”:将老板留下的数放在第一位数,接下来第二位数是队伍末的人的数,第三位数十队伍倒数第二个人的数……最后一位数是排头的数。
(例:若老板留下了248,从牌末往前的编号依次是331,1001,456,……,998,那么该种可能情况的“对应排列”即为248,331,1001,456,……,998)
②.排列的“牛逼度”:对于某一所有数均互不相等的排列,记其牛逼度=(第2位数到末位数中小于第1位数的数的个数)+(第3位数到末位数中小于第2位数的数的个数)+(第4位数到末位数中小于第3位数的数的个数)+(第5位数到末位数中小于第4位数的数的个数)+……+(倒数第2位数到末位数中小于倒数第3位数的数的个数)+(末位数到末位数中小于倒数第2位数的数的个数);
“牛逼度”直观理解为:该排列中所有满足“排在较前的数大于排在较后的数”的数对的总数。
③.“牛逼引理”:对于一个所含数两两不相等的排列,若交换其中两个数的位置得到另一个排列,则这两个排列的“牛逼度”必定一个是奇数另一个是偶数。证明略去。(只需要参考其中不变的地方与变的地方,很方便就能证明出来,如果需要证明我稍后写出)
④.“奇牛逼情况”与“偶牛逼情况”:若一情况的“对应排列”的“牛逼度”为偶数,则该情况为“奇牛逼情况”(反之为“偶牛逼情况”)
接下来就是正文了:
先是几点基础分析
·队伍末的人无论如何在报数之前不可能100%确定自己对应的数,其报数的最大正确可能性为50%,所以要保证999人过,即保证除了队伍末的那一位之外的所有人报数正确。
·因为不能重复报数,又要保证除排列末外的999人全部报数正确,所以排列末的人报的数一定为他没有看到的两个数。(他能看到前方999人的数,排除这些数后剩余两个他可以报的数)
步骤操作概要:
队列末的人从其可选的两个数中选出一个数报出,该数使其所对应情况为“奇牛逼情况”,
队列倒数第2个人,排除所有已经报出的数与所有他看到的排在他前面的人的数,剩余两个未出现的数,从中选出一个数报出,该数使其对应情况同为“奇牛逼情况”,
队列倒数第3个人,排除所有已经报出的数与所有他看到的排在他前面的人的数,剩余两个未出现的数,从中选出一个数报出,该数使其对应情况同为“奇牛逼情况”,
……
队列排头,排除所有已经报出的数,剩余两个未出现的数,从中选出一个数报出,该数使其对应情况同为“奇牛逼情况”,
至此整个队列所有人报数完毕,结果为两种:若队列末的人报数正确,则1000人全体通过;若队列末的人报数错误,则出该人外的999人全部通过。
操作步骤详细解释:
1.
Q:“从其可选的两个数中选出一个数报出,该数使其所对应情况为‘奇牛逼情况’”这句话中的“所对应情况”是指那种情况?
A:即假定此时他对应的数为他所报的数,老板手中的数为他未报的数;其余人中,排在他后面的人对应的数视为其已报出的数,排在他前面的人对应的数视为其后脑勺上贴的数。
2.
Q:“使其所对应情况为‘奇牛逼情况’”,如何保证他一定能选出且只能选出两数中的一个满足“奇牛逼情况”?
A:由上文③“牛逼引理”可知。剩余两个数中,你选一个数与选另一个数,对应的情况必定分别为一个“奇牛逼情况”与一个“偶牛逼情况”。
3.
Q:这种操作步骤为什么能达到其目的保证至少999人通过?
A:反证法:假设之后有人报的数与其后脑勺的数不同,则他报出的数的对应情况与队伍末的人报出的数定下的情况相比,必定只有两个数位置不同,又由于队伍末的人报出的数定下的情况为“奇牛逼情况”,由③“牛逼定理”,他报出的数所对应的情况为“偶牛逼情况”,与操作步骤矛盾。
故“假设之后有人报错数”不成立,所以除了队伍末的人之外,所有在他之后报数的人报的数均与其自己后脑勺的数相同。所以999人保证。
有什么不懂的欢迎再问
当然原帖中关于我这里引入的“牛逼度”也有非常专业的说法,在65楼由youhanyang吧友提供,这位可是很厉害哦,他短时间内完美搞定了【第五层】本人也相当佩服,恩恩。
就是这样,恩恩,各种转发请@


1楼2014-02-10 16:08回复

    卧草肿么会没人啊这不科学


    2楼2014-02-10 18:39
    回复
      楼主起码先把题目说一遍啊,还要让我去百度是什么题目


      IP属地:江苏3楼2014-02-10 19:14
      回复

        这是原帖网址:
        http://tieba.baidu.com/p/2807603749


        4楼2014-02-10 19:17
        回复
          先mark再读


          IP属地:美国5楼2014-02-11 02:33
          收起回复
            你可以跪了。把你的大招收起来解行列式用吧。这种简单的题目用不到它。
            对应结构:对每个ai,总有一个对应法则使它双向对应到aj,且对应法则的个数不超过1001个。
            举例:平均值法。
            两种思路:严格证明对应法则存在,或改进平均值法。
            事实上,对应法则存在即正1001变形可以一笔画走通。详情不证。即存在1001种对应法则使每对数一一对应。(实际上只需要1000种即可,想一想)第一人报的是对应法则的序号即可。
            若改进平均值法,从缺陷入手。缺陷乃对应未利用完全。如平均值是1,1001等。解决方法是补全对应。
            注意到1001是奇数,故出现小数时,可用±500.5消除小数。事实上,这是模1001后同余的数与另一个数的平均数。问题得证。
            你实在理解不了的话,证明以下结论:
            圆内接正1001边形的任意对角线过且只过一个定点。
            然后在定点上写1~1001即可。由于是全射,不存在双射。


            IP属地:山东来自手机贴吧6楼2014-02-11 07:47
            收起回复
              @wrnmsb1h


              IP属地:山东来自手机贴吧7楼2014-02-11 07:48
              回复
                很精彩


                IP属地:四川8楼2014-02-12 16:56
                回复


                  IP属地:山东9楼2014-02-12 19:42
                  回复
                    我需要想想,手机上面不方便,回头再看。再说我的问题贴回复怎么看不到了?消失了


                    IP属地:河北来自手机贴吧10楼2014-02-16 13:59
                    回复
                      来了 看了头大 我才是普通高中生好嘛


                      来自iPad11楼2014-02-26 23:39
                      回复
                        为毛我觉得没有那么复杂啊
                        第一个人说个前面所有人的数字之和,然后第二个人报自己的号(用第一个人报的数减去自己能看到的数之和就能得出自己的号码)依次类推,大家都是报自己的号,走人老板手里的号不影响啊


                        IP属地:安徽12楼2014-03-20 11:12
                        收起回复
                          就是总挑较大的报?


                          IP属地:北京来自手机贴吧13楼2014-04-20 01:29
                          回复


                            IP属地:黑龙江14楼2014-05-19 00:28
                            收起回复
                              除了最末的人,所有人都是三选一,他们怎么知道他的数是最大,最小,还是在中间的?这是问题的关键,楼主似乎审题有问题阿,得出的结论俺有点看不懂呢。


                              来自手机贴吧15楼2014-05-21 05:14
                              收起回复