本人看了动画第二集后才来关注端脑吧(今天刚来的新人一枚),刚刚发现这个帖子,觉得这个题目挺有意思的。
由于这里是端脑吧,我就尝试通过逻辑推理的方式来解决第五层的问题。(首先声明,本人从未看过原题解法,如有雷同,纯属巧合。)
首先,从题目可知,有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个数字排列的逆序数为奇数或者偶数(事先跟其他员工约定好了奇偶)就行了。