脑力小体操:上期答案与π日加餐
majer @ 2020.03.14 , 01:00 下午0.当前的目标是找出所有经理。
1.工程师的人数远大于经理。
2.工程师不会骗人,经理的话不可信。
3.你要在至多99个问题内,100%地确认出一个工程师。为什么?因为只要确认了一个工程师,让他挨个揪出经理就行了!
稍微解释一下,经理的话不可信并不意味着经理就一定说假话。
他们足够精明,又对彼此毫无忠诚可言,为了保全自己混淆视听,会在必要的时候说真话。
所以官方的标准答案是酱紫的
把所有人依照某个顺序拍成一组,比如说编号1、2、3、……、100;将这一组记为初始组。
然后从中随意抽出一人,比如说1号,询问他2号是不是工程师。
如果他说不是,将1号和2号统统抛入一个组,就命名为回收组吧。道理是这样的,这一回答实际上意味着1和2必然有一个不是工程师,所以我们索性将他们两同时放弃。如果能够这样一对对地抛入回收组,那最后剩下的必然是工程师。
如果他说是,就将1号归入一个命名为堆栈的组,然后将2号也归入堆栈!
然后向2号询问类似的问题:3号是不是工程师。
最终,堆栈组里顶端的那位(也是那组里编号最大的)必然是工程师。
为什么呢?
不妨这样思考,比如说最后一个是100号,如果他其实不是工程师,则堆栈组倒数第二位帮他作伪证的必然也不是工程师,然后依次类推,就得到了人数上的矛盾——堆栈组都是经理。
其实,有几位朋友在回复里基本讨论出了如何应用堆栈的思想——本来想把回复里几位给出答案的朋友ID放出来,没想到回复栏那么快就翻页了,而我站回复栏翻页之后,第一页就不见了,淦。
另外有几位朋友,实际上想到了用投票认证的想法。本质上就是让99个员工投票,看剩下那一位是不是工程师。多进行几轮的话,肯定能确定一位工程师。实际上来说,这个思路没啥问题,而且有点拜占庭将军问题的意思。
但是具体到这个问题,它相当于说一次提出99个问题。如果凑巧第一次选出的是经理,则用光了所有的提问次数,又没有确知一位工程师的身份。(虽然有个朋友通过“在纸面圈出所有的经理”这样的提法,把它伪装成了一个问题。)
不过,是我措辞不严谨(其实是故意的啦,就是向让问题开放),而且多轮投票的思想也非常有价值,值得讨论。
最后,本期的锻炼大脑的体操是为3月14日准备的问题:周所众知,π和e(自然常数)是无限不循环小数。有些人(如刘慈欣)相信,它们的小数部分包含所有的、由0-9组成的字段。
现在我问大家,是否能够从π小数点之后某位开始,得到e全部的数字呢?
就是形如这样3.14159……2718281828459……
好吧,上面这个问题或许难以作答,那我们将它视为一个假说吧。
以这个假说为前提,再提出一个容易回答的问题:如果确实能够从π小数点之后某位开始,得到e全部的数字,那么,请回答是否可以从e的小数点某位开始,得到π的全部数字?
就是形如这样2.718281828459……31415926……
PREV : 在安卓系统中复制Java的API,谷歌侵犯了甲骨文的版权吗
NEXT : 大整数分解有了新记录