绿宝书 （翻译）_量化绿皮书

1 Brain Teaser 脑筋急转弯

在本章中，我们讨论的问题只需要常识、逻辑、推理，基本不超过高中水平的数学知识即可解决。 从某种意义上说，它们是真正的脑筋急转弯，而不是伪装的数学问题。 尽管这些脑筋急转弯不需要特定的数学知识，但它们的难度不亚于其他量化面试问题。 其中一些问题会考验你的分析和解决问题的能力； 有些要求您跳出框框思考； 而其他人则要求以创造性的方式使用基本的数学技术来解决问题。 在本章中，我们回顾了一些量化面试中可能遇到的脑筋急转弯问题。

1.1 问题简单化处理

如果最初的问题太复杂以至于您无法立即提出解决方案，请尝试确定问题的简化版本并从它开始。 通常你可以从最简单的子问题开始，逐渐增加复杂性。 您不需要一开始就制定明确的计划。 只需尝试解决最简单的案例并分析您的推理。 通常情况下，您会找到某种模式最终解决问题。

1.1.1 海盗分金

五名海盗抢劫了一个装满 100 枚金币的箱子。 作为一群民主海盗，他们同意以下分配战利品的方法：

最资深的海盗将提议分配硬币。 所有海盗，包括最资深的海盗，都将投票。

如果至少 50% 的海盗（在这种情况下为 3 名海盗）接受该提议，则按提议分配金币。 

如果没有，最高级的海盗将被喂给鲨鱼，这个过程从下一个最高级的海盗开始……

重复这个过程，直到计划被批准。 

你可以假设所有的海盗都是完全理性的：他们想先活下去，然后尽可能多地获得金币。 最后，作为嗜血的海盗，如果可以选择的话，就算自己获得的金币是一样的，他们希望船上的海盗数量越少越好。

金币最终会如何分配？

解答: 5个海盗如果觉得有点复杂，可以从1个开始推理。 

1个海盗不用分，都是自己的；

2个海盗也不用分，资深的（第1个）那个肯定全分给自己，因为自己占50%的投票，所以分法是（Remaining，0）；

3个海盗时，最资深的（第1个）知道2个海盗时，第3个海盗会一枚也得不到，因此会给他一枚，而第2个海盗就别想得到了，因为第1个海盗的策略已经得到2/3人的支持，因此分法是（Remaining，0,1）；

4个海盗时，最资深的（第1个）知道3个海盗时，第3个海盗会一枚也得不到，因此给他一枚获得他的投票，其他两个海盗不给，投票50%也能通过，因此分法是（Remaining，0,1,0）

如此动态推下去，分法是（Remaining，0，1,0,1，..., x） 如果海盗数为偶数，x 为0；否则x为1。  

1.1.2 老虎和羊

100只老虎和1只羊被放在一个只有草的魔法岛上。 老虎可以吃草，但他们宁愿吃羊。 假设： A. 每次只有一只老虎可以吃一只羊，而那只老虎在吃完羊后自己也会变成一只羊。 B. 所有的老虎都很聪明，完全理性，它们都想活着。 那么羊会被吃掉吗？

解答: 同样，100只老虎太多，从少数开始推。

1只老虎，羊肯定被吃，因为老虎吃完羊后变成羊，依然可以活着，没有其他老虎会吃他；

2只老虎，羊不被吃，因为先吃羊的那只老虎会被后面一直老虎吃掉，所以哪一只都不会先吃羊，达成一个平衡；

3只老虎，羊被吃，先想出两只老虎情况下羊会不被吃的那只老虎，会吃了羊变成羊，然后活下去；

4只老虎，羊不被吃，因为剩下3只老虎会吃掉变成羊的那只老虎，所以没有老虎会去吃羊，达成平衡；

如此类推，偶数只老虎时，羊不被吃，而奇数只老虎时，羊会被吃。 回到本题，100只老虎，则羊不会被吃。

这里有点《三体》里黑暗纪元的感觉了。但是里面并没有老虎数量这种全局信息，所以导致的博弈结果是，先开枪。

1.2 逻辑推理

1.2.1 快速过河

A、B、C、D 四个人需要过河。 过河的唯一方法是通过一座旧桥，一次最多可容纳 2 人。 天黑了，他们没有手电筒就不能过桥，而他们只有一个手电筒。 所以每一对只能以较慢的人的速度行走。 他们需要尽快将所有这些人带到另一边。 A是最慢的，需要10分钟才能通过； B 需要 5 分钟； C 需要 2 分钟； D 需要 1 分钟。

那么过河最短的时间是多少，方案是什么？

解答: 这里比较吊诡的或者说反常识的地方在于，快的跟快的，慢的跟慢的组合，更省时间。平时我们的思维范式是，快的带慢的，好的带差的，平均速度或者平均成绩能提上来。这里是影响解这道题的思维定式。 

这道题里设定了慢速的人决定了时间。那么需要换个思路，少浪费就是节约时间。慢的带次慢的，就不会浪费速度快的人时间，也就不会浪费整体的时间。这里换个文言文一点的，叫藏拙。另一个设定是要人送手电筒，肯定要让快的人送，那么方案就出来了。

第一趟，让C、D通过，然后C或者D一个人，返回送手电筒；假设为D，则时间为 2 + 1；

第二趟，让A、B通过，然后C或者D剩下的那个人返回送手电，按第一趟的假设，这次应该是C，则时间为10+2；

第三趟，C、D通过，用时2分钟。

此时，全部人都到对岸，总用时3+12+2 = 17分钟。

1.2.2 猜生日

您和您的同事都知道您的老板 A 的生日是以下 10 个日期之一：

3 月 4 日、3 月 5 日、3 月 8 日

6 月 4 日，6 月 7 日

9 月 1 日，9 月 5 日

12 月 1 日、12 月 2 日、12 月 8 日

A 只告诉了你他生日的月份，并告诉了你的同事 C 生日的号数。 之后，你先说：“我不知道A的生日，C也不知道。” 听完你的话，C回答说：“我不知道A的生日，现在我知道了。” 你笑着说：“现在我也知道了。” 在查看了 10 个日期并听取了您的意见后，您的行政助理没有问任何问题就记下了 A 的生日。 那么助理写了什么？

解答：

你先说：“我不知道A的生日，C也不知道。” ——>月份是重复的，所以“我不知道”，没法判断。这里所有的月份至少都有两个以上，所以只凭这条信息，并不能筛选选项。 “C也不知道”，说明我所知道的月份里，对应的号数都是重复的，这样6月和12月被排除，因为如果C拿到7日或者2日，那就很容易知道生日是哪天。所以现在剩下3月和9月。

紧接着，C回答说：“我不知道A的生日，现在我知道了。” 这句话的前提是C已经推理到月份只有3月和9月，那么C能推出生日，说明肯定不是5号，这样 3月5日和9月5日被排除。

最后你说，“现在我也知道了。”这句判断的前提是知道3月5日和9月5日被排除，还剩3月两天，和9月一天。如果你拿到的是3月，肯定没有信心判断是哪天，那么唯一的可能是你拿到的是9月，所以生日是9月1号。

这里想说两点。第一，不要代入谁说的知道或者不知道，然后纠结他是怎么知道的呢。要跳出这个框框，把他们的话当做判定条件，也就是他们的判断是正确的结果，然后去反推什么情形才能推出这个结果。第二，出题人果然是中国人，猜生日都是领导的生日，领导还俏皮地分别告诉不同的人月份和日子。What a sucker. 猜公司一姐的生日，不更融洽嘛？

类似的逻辑题还有，三个逻辑学家去酒吧，酒保问，“你们都喝酒吗？” 第一位逻辑学家说“不知道”，第二位说“我也不知道”，第三位说“是的，我们都喝。” 这则笑话是用逻辑的严谨性来调侃逻辑学家的死板。重点在酒保问的“都”字上，当前面的逻辑学家不知道后面人的意愿时，他就没法肯定回答“都喝”。同时当他说“不知道”时，也就意味着他自己是要喝的，不然就会直接说“不，我们不是都要喝酒。”，这么简单推下去，说明前面两个人都是要喝的，所以第三个人才敢说“我们都喝”。

类似的还有，学姐问学弟“你们男生都喜欢看爱情动作片吗？”学弟脸一红，说“不知道”。学姐眉毛一挑，不怀好意地用第二声调拖长音说“哦~~~”

1.2.3  花色牌

赌场提供使用一副普通 52 张牌的纸牌游戏。 规则是你每次翻两张牌。 对于每一对，如果两者都是黑色的，则进入庄家的牌堆； 如果两者都是红色的，它们会进入你的堆； 如果一黑一红，则丢弃。 重复该过程，直到你们两个通过所有 52 张卡。 如果您的牌堆中有更多牌，您将赢得 100 美元； 否则（包括牌数相同的情况）你什么也得不到。 赌场允许您协商要为游戏支付的价格。 你愿意花多少钱来玩这个游戏？

解答：Not a tiny little rat's ass. 一毛钱都不给。

不管怎么发牌，最终牌数都是相同的，按照他的规则，你什么也得不到，但是你输了玩游戏支付的价格。

怎么理解不管如何，最终牌数都相同？

假设两种极端情况，第一次，每一种都是一黑一红，那么牌都丢弃了，你们牌数都为0；第二种，每次发牌都是同色的，不是红红就是黑黑，那么你们最后牌数都是26张，也相同。

那有较真的，如果不是这两种极端情况呢？怎么证明。

我们假设黑牌得分为-1，红牌得分为1，那么一副牌加总得分为26+（-26）=0。当两张牌为黑时，得-2分；红牌时得2分；一红一黑得0分，丢弃。所以最后，不管庄家（赌场）得多少分，你只能是得对应的负分。但是绝对值相同，也就意味着牌数相同。

这里关键的设定是当牌数相同时，你是输的。类似的庄闲点数相同时庄家剩的设定，也是有偏的。只要庄家有足够的实力能永续玩下去，输的肯定是赌鬼。

1.2.4 烧绳计时

你有两根绳子，每根绳子都可以燃烧一个小时。 但是任何一根绳子密度不均，密的地方烧的慢，疏的地方烧的快，不能保证绳子不同段燃烧速度的一致性。 你如何用这两条绳子测量 45 分钟？

解答：烧两头。

首先点燃一根的两头和另一根的一头，开始计时。当两头烧的烧完了，计时半小时，同时点燃另一个绳子的另一头，让它也两头烧，重新计时，当它烧完时，计时15分钟。两个加起来就是45分钟。

这里需要理解的是，当两头烧不均匀的绳子时，他们空间上不会在一半的地方相处，稀疏的火头走的快，碰头的时候肯定烧的绳子更长。但是他们时间上肯定是在一半的时间上相遇，假设他们燃烧都是充分的。这是一个相遇问题，想象两个人相向行走，能更容易理解。

1.2.5 用天平区分次品球 

有12个球，其中有一个球是次品，跟其他球的重量不一样，是更重还是更轻不清楚。现有一个天平，请问用3次天平测量，如何测出次品球来，并区分是重还是轻。

解答：此题比较复杂，逻辑环环相扣。总体思路原则有一下三点。

a, 三分组，对比其中两组，可以揭示第三组的信息；

b, 借助已知球来构造中间步骤的分组，减少不确定性；

c, 剩下待确定的球中，如果有两个球可能有同样的问题，直接对比此两球；否则对比其中一个跟已知球的关系。

此题讲解起来比较费神，图表可能更清晰，等日后做个图上传上来。

另外，这里面有规律，如果球的缺陷类别（重或轻）已知，则可以用M次测量区分3^M 个球中的一个次品球；如果缺陷类别未知，则可以区分(3^M-3)/2个球中的一个次品球。 （公式推导？）

1.2.6 阶乘尾0的个数

100！的尾部有几个0？

解答：首先分析相乘产生0 的情况。2*5 = 10； 4*25 = 100 =4*5*5。 也就是一个5乘一个偶数就能得到1个0，偶数比5的个数要多得多，所以0的个数，取决于能分解出多少个5。那么（5,10，...,100）能分解出多少个5？

首先（5,10,...，100）除以5，有（1,2，...，20），含20个5，另外（1,2，...，20）中还有4个5，因为（5,10,15,20），除以5有（1,2,3,4），没5了，所以总共含有24个5，也就是有24个0。

那么1000！呢？

[5,1000] |200 + [5,200]|40 + [5,40]|8 + [5,8]|1 = 249个

1.2.7 无限序列

x^x^x^x^x · · · = 2,  x^y = x的y次方，求 x

解答：无限序列的情况，用迭代的思想列方程，x^x^x^x^x^x · · · = x^(x^x^x^x^x · · ·) = x^2 = 2

所以 x = 根号2。

另外，如果列成x^x^x^x^x^x · · · = （x^x^x^x^x）^x · · · = 2^x = 2, 所以x=1。 将x=1 带进去，得1=2，不成立。这是为什么呢？ （x^x^x^x^x）这里是有限序列，它不等于2.

1.3  跳出思维的框框

1.3.1 打包箱子

请问能否把53块1X1X4的砖块放到6X6X6的箱子里？

解答： 6x6x6的箱子体积为216，砖块掰碎了能装54块。但是成型的，放不了53块。

这题是国际象棋题的升级版。国际象棋的题目是二维的，而箱子是三维的，更难一些，但是解法都是一样的。从国际象棋题展开来说。

如图象棋棋盘是黑白相间的64个小方格，假设都为1x1，现在拿去对角线上的两个小方块，请问，还能否放入31个1x2的方格进去？

棋盘天然是黑白相间的，很容易理解，不管怎么放1x2的方格，都会占据1黑1白两个方格。那么最多能放几个1x2方格，取决于黑格或者白格的数量最少的那个。本来64个，黑白各32个，但是移除对角线的两个方格，是同颜色的，那么就还剩下30个黑32个白，或者30个白32个黑，所以不论什么情况，最多是30个，占据的面积是60，有两个不相连的方格剩下。

按照这个套路，解决箱子问题。虽然知道了要用配色法去解决，但是如何构造还是挺巧妙的。砖块是1x1x4的，我们为了一个砖块穿越2个色块，那么色块的高度应该为2（4的一半），又因为箱子是个正方体，那么应该用小正方体给它上色，也就是2x2x2的小箱子。这样的小箱子总共有3x3x3=27个，然后他们颜色相间的话，只能是13黑14白或者13白14黑。同时因为两个黑白的小箱子能装4块砖（底面积是4倍），所以总共能装的是13x4 等于52块砖。注定有一块2x2x2的小箱子浪费。

1.3.2 日历骰子

用2个自制的骰子（6面），刻画所有月份里的天数，仅仅是天数。其中第一天为01，一个骰子显示0，一个显示1。那么请问该如何设计这两个骰子。

解答：就是俩个骰子各个面应该刻什么数。0-9十个数，骰子12个面，还剩两个面给重复的数，也就是11号，22号。1和2 两个骰子都要刻。然后前9天是01，02，...，09，如果只有一个骰子刻0，那么肯定无法展示所有这9天，因此0也要两个骰子都刻。那么问题来了，12个面，刻0，1，2就用了6个面，还剩下6个面要给7个数字，怎么刻。

脑筋急转弯来了，6和9是对称的……只要刻一个数字就可以表达2个数……，所以一个刻012345，另一个刻012678……

这题其实能分析出012都要刻就已经成功了。对称这个考点，有点小聪明的感觉，但也挺巧。

1.3.3 offer之门

假如两个守卫守着两扇门，一扇通往offer，一扇“谢谢你的投递，but you failed”。两守卫一个诚实只说真话，一个狡猾只说假话。你只能问其中一个

守卫一句只能用yes/or回答的问题，你如何问，才能顺利打开offer之门？

解答：你不知道谁守着那扇门，有可能是诚实的守着offer之门，有可能是诚实的守着you failed之门，那么单独问任何一个“这是offer之门吗？”这种傻白甜的问题，是无法得出明确信息的。解题的关键在于把两个守卫关联上——你问其中一个守卫“另一个守卫会说你守的是offer门吗？”，如果该守卫说是的，则选另一扇们，如果说No，那就是这扇门。

分析路径是：

如果你问的是诚实守卫且他守的是offer之门，那么另一个守卫会撒谎说No，而这个守卫只说实话，只能原原本本告诉你另一个守卫会说No，这扇是offer门；

如果你问的是狡猾守卫且他守的是offer之门，那么另一个守卫会实话说yes，但这个守卫只说假话，会篡改另一个守卫的原话然后说No，这扇也是offer门；

如果你问的是诚实守卫且他守的是failed门，那么另一个守卫会说谎话说yes，而这个守卫只说实话，只能如实转告另一个守卫说的是Yes，这扇是failed门；

如果你问的是狡猾守卫且他守的是failed门，那么另一个守卫会说实话说No，但这个守卫只说假话，会篡改另一个守卫的原话然后说Yes，这扇是failed门。

找到规律了，问“另一个守卫会说你守的是offer门吗？”不管他是哪类的，守着什么门，只要他回答No，就是offer门；回答yes就是failed门。

上面的分析，是慢速思考系统分析出来的。我们需要用直觉快速系统总结一下，培养直觉。

1、问法要联合两个守卫，且直接问关心的offer门；

2、回答是的，往往是陷阱，是failed；而回答no的，往往是candy，是offer之门。

1.3.4 挂锁快递

你想给上海的朋友发快递送物资，但是最近时局动荡，没上锁的快递不安全，东西会丢，需要用挂锁箱子运送。但是目前你跟你朋友各自有一把锁，但是各自都只有一把钥匙，那么应该怎么送，物资才能安全送达？

解答：没有限定送的次数，只要求安全。那么第一趟送的时候挂你的锁，安全送到上海，但是你朋友打不开。没关系，你朋友很聪明，在箱子上又挂了一把他自己的锁，然后快递送回来，你把自己的锁解开，再快递到上海，这时候，就是你朋友的锁在保护物资了。平安到上海后，你朋友就可以打开箱子获得物资了。

这题主要在于可以运送多次，也可以看见为了安全带来的效率下降。这题类似信息安全的握手机制。各自上一道锁，然后先后解开，才能确保这个信息是你们俩的。

1.3.5 最后一球的颜色

如果袋子里有20个蓝球，14个红球。每次抽两个球，不放回，扔掉。如果抽出的是同色的，往袋子里添加一个蓝球；如果是不同色的，则添加一个红球。假设球足够

进行这些操作。请问，袋子里最后一个球是什么颜色的？如果是20个蓝球，13个红球呢？

解答： 观察各个组合带来的蓝球和红球的变动规律，蓝球奇数变动，要么加1要么减1；红球要么不变，要么减2，都是偶数变动。所以如果14个红球的话，最后肯定变成0，

那么剩下的是蓝色球；如果红球是13个，那么剩下的最后是红球。 就看奇偶性。

思路上是比较清晰的：知道初始状态，想知道最终状态，那么我们就需要理清楚状态转换规则是什么，从中找到转换的规律。

1.3.6 控制灯的开关是哪个

屋外有四个开关，屋内有一盏灯，其中只有一个开关控制灯。你在屋外不能及时看到灯的状态。请问至少需要进屋几次才能分辨出控制灯的开关是哪个，该如何操作。

解答：灯除了明灭的信息，还有冷热的信息，灯开一段时间会发热，这层信息也要利用上（就算不是白炽灯，节能灯也会发热）。那么两种状态（亮否，热否）可以表示四种可能情况。我们需要设计这四种情况对应四个开关，这样就可以以最少的进屋次数，分辨出控制开关。 控制明灭是即时的，而控制是否发热则需要一定时间；

那么我们可以先闭合1和2开关，等待一段时间。然后把开关2断开，合上开关3，立即进屋查看灯的两种状态。判断规则如下：

a 如果灯是亮且热的，那么开关1控制；

b 如果灯是亮但不热的，那么开关3控制；

c 如果灯是暗但热的，那么开关2控制；

d 如果等是暗且不热的，那么开关4控制。

这里断开开关2，闭合开关3的操作很重要。那么是怎么想出这一步的呢？开关1和2先开一段，如果发热，肯定是1或者2控制的；那怎么判断到底是哪个控制的，就需要借助明灭的状态来区分，所以我们需要把其中一个开关断开，这里选择了开关2。但是这里还不够，如果不热的话，能排除开关1和2，但是究竟3和4哪个依然分不清。这时我们需要闭合3或4其中一个开关，同样借助明亮来区分，这里我们选择了闭合开关3。所以两头一推，就能推出断开1或2中的一个，闭合3或4中的一个这个关键操作。

1.3.7 求量化平均工资

5个量化工程师去酒吧喝酒，他们好奇量化行业的平均工资是多少，但是又不想暴露自己的收入情况。请问有什么方法可以在不暴露各自收入的情况下，求得他们的收入均值？

解答： 第一个工程师设置一个随机初值，写上自己的收入与初值的加和，然后传递给第二个工程师；第二个工程师也加上自己的收入，依次加总完后，将数据给第一个工程师，他将最后的总数减去随机初值，然后除以人数，就是他们收入的均值。这里并没有泄露任何人的真实收入。

随机初值设定有一定要求，跟真实收入相比不能太小，不然也会泄露你的大致收入。初值设为工资的3到10倍为宜，太大也不行，比如你设定个十亿，然后传给第二个人的数是10亿48万，傻子也能猜出个大概。

另外也不能请酒保或者路人等第三方进行汇总，这样有数据泄露的风险。1对N的数据归集方式，这个“1"的道德风险就需要考量。而本题所提的串行加总的方式，不用担心这类问题。

这种通过设定随机初始值的偏移量，起到保护数据隐私的方式，在实际生活中也是比较常见的。

1.4 巧用对称性

1.4.1 确保两堆硬币有同样数量的字面朝上

假设有1000个硬币，其中有20个字面朝上，980个花面朝上；你不能通过触摸感受硬币是哪一面，但是你可以无限次数的翻转硬币。请问怎么分，才能确保分出来的两堆硬币字面朝上的硬币数量相同？

解答：这里不要给自己加戏，增加难度，以为是要平分成两堆，而且字面朝上的数量相同。这里只要求分成两堆，并没有要求平均分。这是我自己解题容易出现的思维定势。

好的，我们假设给第一堆分了n个硬币，其中有m个字面朝上的，那么另一堆则有1000-n个硬币，其中20-m个字面朝上。我们要确保两边的字面朝上，且手段只有翻面。那么

我们只需要第一堆里的n个硬币都翻过来，则n-m个花面朝上的翻过来成了n-m个字面朝上的硬币，数量要等于第二堆里的20-m个，那么可以知道n=20。第一堆里剩下的m个原本字面朝上的则变成了花面，但是我们并不用在意。所以方案是从1000个硬币中随机选20个，不管这20个里面是否有字面朝上的硬币，都给翻转过来，就能保证这两堆里，字面朝上的硬币数量相等。

培养直觉：原本有多少个字面朝上的硬币，就随机选多少个硬币成堆，然后全部翻面。

1.4.2 打错标签的水果袋

有三袋水果，分别装着梨、苹果以及苹果和梨的混装。每个袋子外面打了相应的标签，但是现在水果店老板告诉你，标签都打错了，你可以拿出水果来判断袋子的正确标签，那么请问怎么拿最少次数水果，更正所有的标签？你可以拿无数次，袋子是非透明的。

解答：这里用的是对称思想：标记苹果和标记梨的袋子其实是无差别的，因为我们不知道里面到底是哪一种水果还是混装水果，所以我们不应该先从标记梨或者苹果的袋子里拿水果进行验证。于是我们应该从标记为混装的袋子里拿水果，拿出来的是梨，那么这个袋子里装的就全是梨；拿出来的是苹果，那么这个袋子里装的就全是苹果。它不会出现混装的情况，因为题目告诉了，所有标签都错了。假设我们从混装袋子里拿出的是梨，那么标签为梨的袋子里装的肯定是苹果。为什么？因为如果它是混装的话，剩下标签为苹果的袋子里装的肯定就是苹果了，与题设所有标签都错不符。最后标签为苹果的袋子里装的是梨。逻辑如下表所示：

这题可以深挖一下。不选单纯的梨或者苹果标签，而选择混装的做法，里面除了上述的逻辑，还有更深的含义。

戏谑的版本是，某教辅机构流传的选择题秘诀：两短一长选其长，两长一短选其短。这个秘诀没什么逻辑，但跟这道题有形似之处。

更学术的表述是，单一的表述所带来的信息量（信息熵）不如混合表述的信息量高。比如你通篇140个字都是“啊啊啊啊……”跟你用心写140个字的状态相比，肯定是后者的信息量更高。

更物理一点的表述是，明确、单一的耗散结构需要能量去维护，随着时间推移，宇宙熵逐渐增加，耗散结构将消失，演变成一种寂灭的状态。这种寂灭就是一种混合状态，所有的粒子最终都会变成随机游走的状态，这也就是宇宙的尽头。

1.4.3 50智者斗酋长

野人酋长抓了50个智者。每分钟他随机抓一个智者去问话，问话前每个智者可以翻转大堂门口的一个玻璃杯，也可以不翻转。如果智者可以肯定地正确地回答“所有智者至少被酋长问过一次话”，那么酋长会放了所有人。否则，回答错误的话，也就是说不是所有人都被问过话，但有智者回答是，那么所有人会被献祭。在他们被关到各自牢房（一人一间）前，他们可以聚集一次商量对策。 那么智者该如何应对才能活下来。被问话的智者是随机且无限次抽取的。不回答不视为答错，智者在没把握的时候可以选择不回答。

解答：50个人都是智者，是同质的。所以随机选一个作为回答者，或者发言人，我愿称之为破题人。其他剩下的49人都是同质的，操作和规则一致。那么破题人需要跟其他49人约定一个标定任何一个人初次被问话的判断规则。这个规则是你第一次被喊话，一定要做标记，之后被喊话就不用再做标记以免干扰，另外这个标记还必须被破题人发现，并由破题人归置为初始状态。那么只用一个杯子正放与倒放来做标记，也就是一次只能标记一个人。那多次归置，破题人进行统计即可。 按照上述原则，他们商量出了一套规则，如下表所示：

此题需要充分利用“无限次随机问话”，进行信息串行的传递。每个人有且只有一次传递自己信息的机会，传递的前提是“杯子是正放的”，这说明别人没在传递信息，因此“我”进行信息传递，不会干扰别人传递消息。在“我”传递消息后，会随机抽到其他人，甚至可能是自己，此时杯子是倒置的，大家都不进行操作，直至破题人被随机抽到，然后归置杯子，累计信息，等待下一个人传递自己的信息，直至49个人信息都被收集成功。

1.5 数列求和

1.5.1 钟表碎片

一块钟表刻度为1,2，...，12，摔碎成了连续的3块，且每块的刻度数字和相同，请问碎成了哪三块？

解答：钟表刻度总和为sum（1，...，12）= 13*12/2 = 78， 碎成和相同的三块，那么每块数字和为26。其中刻度最大为12，碎片又是连续的，那么第一块肯定是11,12,1,2；那么往两边推，11点前面的是10,9，加8就超过26了，然后2点往后是3,4, 所以第二块是9,10,3,4；剩下的为第三块，7,8,5,6。

想象一下这个摔碎的样子，不是披萨类型的尖尖角，而是饼干那种不均匀的碎法，11,12，1,2碎一小块，7,8,5,6碎一小块，剩下的一大块。题目说的是连续的三块，不要定势成均匀的三块。

第二，连续的三块，说明刻度也是连续的，所以很容易想到11，12 和1,2，然后分别顺时针与逆时针进退两位就行，保证两数加起来为13。

1.5.2  缺失的整数

1到100个整数里，缺了两个，问怎么快速得到这个缺失值？

解答：原题答案是用解方程的方式，分别求一次和和二次和，列两个方程，然后解方程。中学生的难度。原答案还提到编程实现是O（n）复杂度。如果编程的话，不用列方程，直接哈希查找就行，也是O（n）。

1.5.3 快速定位劣币袋子

有10袋子硬币，每袋100个硬币，每个真币重10克。其中有一袋的硬币全是假币，可能比真硬币重1克，也可能轻1克（全都重或者全都轻）。现在有个电子秤，请问如何用最少的次数称重，找出假币的袋子？

解答：问题转为，如何通过硬币快速给出劣币袋子的信息？

袋子里只有硬币，而且单个硬币是同质的，那只能依靠数量来区分袋子了。 第一个袋子拿1个硬币，第二个袋子拿2个硬币，如此类推，第10个袋子拿10个硬币；这样假硬币的数量就能反向指出袋子的编号。

具体做法显而易见，把所有硬币汇总，称一下，如果小于550克，则说明假币轻了，而且假币袋子编号为550-实际称重；

如果大于550克，则说明假币重了，假币袋子的编号为实际称重-550。

这类题是用连续数列来区分袋子编号，类似的还有用二进制序列来区分试剂药品之类的题。比如有1000罐药，其中有一罐有毒，一点就致命，但是需要一天才能显现效果，现在有10只小白鼠，问该如何测试，才能最快把毒药辨别出来？方法是混合试剂，用2进制的方式混。如第9罐药，对应10位的2进制为“0000001001”，也就是喂第7只和第10只小白鼠喝第9罐药（一丁点）。如此类推，将药罐的编号变换为对应的10位2进制，然后为1的数对应的小白鼠喝药，最后看小白鼠的死亡pattern，转换成对应的二进制数，再换算成药罐的序号，就可以在一天内找到毒药。

不管是连续序列，还是2进制变换，本质是要找到一种传递信息或者区分的方式。

1.5.4 100楼层测试玻璃球硬度

假设你有两颗玻璃球，楼有100层，采用楼层高度表述玻璃球的硬度。当球从小于X层往下掉时不会碎，而当从大于等于X层处下落时会碎。那么考虑最坏的情况，应该怎么测试才能最小化球下落的次数，从而测试出玻璃球的硬度。

解答：假设最坏情况，我们至少要扔N次玻璃球。第一球从N层下落，如果碎了，第二个球从1层开始测到N-1层，肯定能测出X；如果第一球层N层下落，没碎，那么下一步，需要从第N+N-1层下落进行测试，因为如果碎了，另一球可以从N+1层测试到2N -2层，测试N-2次；如此类推，第一球如果没碎，则每次间隔减少1层，直到在N次测试时，覆盖100层楼，也就是 N+（N-1）+(N-2)+... + 1 >=100, 求得N>=14，取最小值14，也就是最少扔14次，不论怎么样，可以测出球的硬度。

此题核心在于理解“什么是最坏的情况”。

先不管什么情况，扔球的策略肯定是从底层往高层逐步测试。如果直接上高层，第一个球碎了，剩下的就只能一层一层往上测试。

那么最好的情况是，X=1，也就是一层扔下，球就碎了。只需一次测试，就成功了。但是X并不一定为1，那么我们就要考虑最坏的情况，也就是X很高，但是测试方法（如上所述）还是得从下往上。那么我们就要优化从下往上的间隔变动方案，这样才能有个最小次数的概念。不然就一层一层扔（只有一个球的情况），或者隔一层扔（有两球的情况），这种方式肯定能测出X来，但是次数会很多。

那么接下来，我们就要分析怎么间隔才能次数最小。换个表述方式就是，不管遇到什么情况（不管X在哪儿），我们都能以这个最小次数N测出来。那么第一次我们间隔N-1 次，看第一个球从N层落下的情况；如果落下不碎，那么就变成了剩下的楼层里最少N-1次测完，间隔应该为N-2,；如此类推，直到所有楼层被覆盖。

1.6 鸽笼原理

n只鸽笼，mn+1只鸽子，分配到各个鸽笼里，至少有一只笼子里的鸽子不小于m+1只，也就是至少有m+1只鸽子要共享一只笼子。

1.6.1 袜子成对

假设你有黄绿红三色袜子x, y, z只（x，y，z均大于0，x+y+z>3），请问随机取，取多少次一定能配上一对？

解答：假设最差情况，取了三只，都是不同颜色的，那么再取一只，肯定是三色中的一种，即可配对，也就是取4次，一定能配上。

这里面把不同色的袜子种类数看成不同的鸽笼，3种袜子等于3只笼子；将袜子看成鸽子，那么只需4只袜子，就会有一对共笼。这种知识迁移方式其实有点不大严谨，笼和鸽子都是同质的，但是不同色的袜子，直觉上并不应该看成是同质的。简单来说两只鸽子同笼了，可以直接说是一对；但是两只袜子放一块，并不一定是一对，有可能是不同花色的。当然这里应该理解成拿了第四双袜子，然后人为地给它选择同色的那一只笼子（袜子）。

这题从集合的角度，也许更恰到好处。这里只有3类元素（类别是异质的），当你取四个元素时，肯定至少有两元素是同类的。

1.6.2 是否有两人握手次数相同

假如你是新上任的领导，第一次去见你的n个团队成员，他们列成一排一 一跟你握手。同时他们之间也有新来的相互不认识也会互相握手打招呼。那么请问你是否能肯定地说，“这些人中，至少有两人握手的次数是相同的”。

解答：能。 团队加上你总共n+1人，然后跟你一 一握手，握手次数的集合为{1,2，...,n}，不包含0是因为所有团队成员都跟你握了手，所以握手次数至少为1。那么不管他们之间如何握手，假设n个人分别握手的次数为1,2，...,n，并不相同，但第n+1个人，他的握手次数肯定落在这个集合内。因此可以肯定地说，至少有两人握手的次数是相同的。

这里把握手的次数看成笼子，人看成鸽子，说n个笼子，n+1只鸽子，肯定有同笼的。把握手次数看成笼子需要解释一下，把抽象的东西比喻成具象的，并一定总是会很形象。可能不如用集合，更贴切。

1.6.3 我们之前见过吗

晚会上有6人，证明要么至少3人是熟人，要么至少3人是陌生人。

解答：选四个人，如果两两认识或者两两不认识，那么都满足要证明的结论；如果四人中，三个相互认识，或者三个互不认识，也直接满足要证明的结论；如果四人中，两人相互认识，两人互不认识，那么判断另外两个人的关系，如果他俩认识，那么就归在认识的一群中（四个人），如果不认识，则归在不认识的那两人集合中（四个人）。第三种情况有种鸽子同笼的味道。

注意，A认识B，C认识D，但A、B与C、D并不相识，也认为熟人有四个，尽管他们并不是两两都相识。

TBC