第二章 脑筋急转弯
本章讨论一些只需常识、逻辑推理和基本数学知识就能解决的问题。虽然这类问题通常不需要专门的数学知识，但它们并不比其他量化面试题更容易。其中一些问题会考察你的分析能力和解决问题的技巧：如果你能够运用基本数学方法创造性地解决问题，会给面试官留下很好的印象。本章也借助这些面试题说明若干通用的解题思路，以便你在实际量化面试中迅速把握问题的关键。
2.1 问题简化（Problem Simplification）
如果原问题过于复杂，让你无法立刻找到解法，就试着先构造一个容易入手的简化版本。通常，只要从最简单的子问题开始，即使一开始没有明确的完整计划，也能逐渐找到规律。先分析这些简单情形，往往比始终纠结于原问题更有帮助。
海盗分赃（Screwy pirates）
题目： 五名海盗找到一个装有100枚金币的箱子。他们决定用以下方法分配战利品。
资历最深的海盗首先提出分配方案。所有海盗（包括提出方案者）都参与投票。如果方案获得至少50%的赞成票，海盗们就按方案分配金币；否则，提出方案的海盗会被扔去喂鲨鱼，然后由剩余海盗中资历最深的人提出新方案，如此反复，直到某个方案通过。你可以假设所有海盗都完全理性：他们希望活命、尽可能多地得到金币，并且嗜血——如果在其他条件相同的情况下可以少留一名同伴，他们就会选择这样做。
五名海盗最终会怎样分配金币？
查看解答
解答： 如果你没有学习过博弈论或动态规划，这个问题可能看起来令人望而生畏。如果直接考虑五名海盗，可以先用只有两名海盗的简化版本入手。
按资历从低到高给海盗编号。只剩两人时，2号海盗只需自己的一票就达到50%，因此他可以独得全部金币，1号海盗一无所获。
再增加一人：如果3号海盗的方案被否决，1号将一无所获。于是3号只需给1号一枚金币，就能赢得1号的支持，自己留下99枚。此时3号获得两票，方案通过。
如果有四名海盗，4号知道自己一旦被淘汰，2号在三人局中将一无所获。因此，4号给2号一枚金币，自己留下99枚，就能得到两票，即50%的支持。
最后考虑五名海盗。如果5号的方案失败，3号和1号在四人局中都得不到金币。因此5号只需分别给1号和3号各一枚金币，就会获得三票（包括自己的一票）。最终分配为：5号98枚，4号0枚，3号1枚，2号0枚，1号1枚。
从这个问题出发，还可以推广到更多海盗的情形。一旦超过五人，答案会更有意思。对于
老虎与绵羊（Tiger and sheep）
题目： 一个只有青草的神奇岛屿上，生活着100只老虎和1只绵羊。老虎既可以吃草，也可以吃绵羊。假设：A. 每只老虎只要吃下一只绵羊，自己就会变成绵羊；B. 所有老虎都十分聪明、完全理性，并且都想活下去。那么，这只绵羊会被吃掉吗？
查看解答
解答： 100是一个较大的数字，先考虑简化版本。如果只有一只老虎（
如果有三只老虎，其中一只吃掉绵羊并变成绵羊后，岛上还剩两只老虎，而这两只老虎不会吃掉绵羊。因此，三只老虎时，第一只老虎会吃绵羊。如果有四只老虎，一只吃掉绵羊后就会变成绵羊，剩下三只老虎会吃掉它；因此没有老虎会吃绵羊。
按同样的逻辑，可以用归纳法说明：老虎数为偶数时，绵羊不会被吃掉；老虎数为奇数时，绵羊会被吃掉。 由于
2.2 逻辑推理（Logic Reasoning）
过河（River crossing）
题目： 四个人
四人全部过桥所需的最短时间是多少？
原书提示 ¹： 关键是让10分钟的人和5分钟的人一起过桥，而且不能在第一次就这么做；否则其中一人还得返回。
查看解答
解答：
生日问题（Birthday problem）
题目： 你和同事知道老板
| 月份 | 候选日期 |
|---|---|
| 三月 | 4日、5日、8日 |
| 六月 | 4日、7日 |
| 九月 | 1日、5日 |
| 十二月 | 1日、2日、8日 |
查看解答
解答： 不要猜；只需利用每个人发言及其先后顺序所透露的信息。
设
你得知
扑克牌游戏（Card game）
题目： 一家赌场提供这样一种游戏：使用一副标准的52张扑克牌。每次翻开两张牌；如果两张都是黑牌，它们归庄家；如果两张都是红牌，它们归你；如果一红一黑，就把这两张牌丢弃。如此进行，直至52张牌全部用完。如果你手中的牌比庄家多，就赢得100美元；否则（包括双方牌数相同），你什么也得不到。庄家允许你付费参加。你最多愿意付多少钱？
原书提示 ²： 尝试从对称性入手。每一对被丢弃的牌都恰有一张红牌和一张黑牌。被丢弃的牌使你和庄家剩余可得的红、黑牌数量发生了什么变化？
查看解答
解答： 这个游戏的规则暗藏玄机。不管牌如何排列，你和庄家最终拿到的牌总是一样多。因为每次丢弃的牌都包含一张红牌和一张黑牌，所以丢弃后剩余红牌与黑牌的数量始终相同。最终，分配给你的红牌数一定等于分配给庄家的黑牌数。庄家永远都会赢。因此，不应该为这个游戏支付任何费用。
燃烧的绳子（Burning ropes）
题目： 有两根绳子，每根绳子从一端烧到另一端都需要1小时。但每根绳子的不同部位燃烧速度可能不同，所以无法保证相同长度的绳段需要相同的燃烧时间。如何仅用这两根绳子测量出45分钟？
查看解答
解答： 这是一道经典脑筋急转弯。如果一根绳子从两端同时点燃，它会在
异常球（Defective ball）
题目： 有12个外观完全相同的球，其中1个重量异常（可能偏重，也可能偏轻）。你只有一架天平，且最多只能称3次。能否找出异常球，并判断它偏重还是偏轻？
原书提示 ³： 先考虑已知异常球偏重时，如何在9个外观相同的球中只称两次找出它。
查看解答
解答： 这也是一道经典的脑筋急转弯，至今仍被许多面试官采用。不同版本的题目里，球的数量从8个到100多个不等。这里用12个球来说明基本思路。关键在于：将原来的12个球（以及后续可能出现的子问题）尽量分成三组，而不是两组，因为比较其中两组的结果也会提供关于第三组的信息。
为了把解法解释清楚，图2.1给出了一棵完整的决策树。把12个球编号为1至12，先分成三组，每组4个。第一次称重时，将1、2、3、4号球与5、6、7、8号球进行比较。接下来重点考虑两种情况：两组重量相等（用“=”表示）；或者1、2、3、4号球比5、6、7、8号球轻（用“−”表示）。如果1至4号球更重，只需对调两组球的编号，即可用对称的解法处理。
如果第一次称重平衡，则异常球一定是9、10、11、12号中的一个，可能偏重（H），也可能偏轻（L）。第二次把9、10号球放在一侧，8、11号球放在另一侧；我们已经知道8号球是正常的。如果9、10号这一侧较轻，说明9号或10号偏轻，或者11号偏重。第三次只需比较9号与10号：若9号较轻，则9号是偏轻的异常球；若两者平衡，则11号偏重；若9号较重，则10号偏轻。如果第二次平衡，则12号就是异常球，第三次将12号与正常的8号球比较，即可确定其偏重还是偏轻。如果第二次9、10号这一侧较重，则9号或10号偏重，或者11号偏轻，也可用第三次称重分辨。
对于第一次称重不平衡的情况，图2.1的另一条分支给出了对应操作。图中假设1、2、3、4号较轻，此时它们中的异常球只能偏轻，而5、6、7、8号中的异常球只能偏重。第二次称重比较1、2、5号与3、6、9号（9号是正常球）；根据天平的三种结果，把可能的异常球缩小到至多三种情况，再通过第三次称重确定球的编号及轻重。
根据这棵决策树，全部可能情形都能在三次称重内解决。
更一般地说，如果已知异常球偏重还是偏轻，那么最多可以用
原书提示 ⁴： 这里利用了对称性。1、2、3、4与5、6、7、8的编号并无特殊之处。若1、2、3、4较重而5、6、7、8较轻，只需交换两组的标记，便可得到5、6、7、8较重而1、2、3、4较轻的对应情形。
末尾零的个数（Trailing zeros）
题目：
查看解答
解答： 每一对因子2和5都能产生一个末尾零。将
赛马（Horse race）
题目： 有25匹马，每匹马都以各自固定的速度奔跑，且速度互不相同。跑道只有5条，因此每场最多只能让5匹马比赛。如果只能知道每场比赛的名次，最少需要比赛多少场，才能找出跑得最快的3匹马？
原书提示 ⁵： 不妨假设各组内的马按下文所述的顺序排列。如果实际顺序不是这样，只需重新编号即可，不影响解法的普遍性。
查看解答
解答： 先将25匹马分成五组，每组5匹，共赛5场。假设按速度由快到慢，各组名次分别为1—5、6—10、11—15、16—20、21—25。例如，第一组中1号最快、5号最慢。前5场结束后，有些马就可以直接排除了：6、11、16、21号分别是所在组最快的马，而它们组里的其余马都不可能比它们更快。
但目前还无法确定各组之间的相对快慢。即使一匹马在自己的组中排名第四或第五，也不能仅凭组内名次判断它是否进入总体前三。
第六场，让五个小组的第一名——1、6、11、16、21号——同场比赛。不失一般性，假设本场排名为1、6、11、16、21。此时可立即排除4、5、8、9、10、12—15、16—20及21—25号：它们前面至少已有三匹更快的马。1号必然是总体第一，进入前三的另外两匹只可能是2、3、6、7、11号。
让这五匹候选马再赛一场，取前两名即可。因此，总共需要7场比赛，分三轮完成。
无限幂塔（Infinite sequence）
题目： 如果
求
查看解答
解答： 这个问题乍看比较困难，但稍作分析就能得到简洁的结果。原式是无限重复的结构；去掉最外层的
于是
2.3 跳出框架思考（Thinking Out of the Box）
装砖块（Box packing）
题目： 能否将53块尺寸均为
查看解答
解答： 这是经典棋盘问题的一个巧妙的扩展。先考虑较简单的情况：在一块
画出真正的棋盘会更容易理解（见图2.2）。黑白格交替排列，棋盘原本各有32个黑格和白格。两个对角格颜色相同；将它们移除后，只剩30个黑格和32个白格。每块多米诺骨牌都必须覆盖一个黑格和一个白格。如果只铺30块，就会剩下2个白格；第31块不可能在不重叠、不越界的情况下同时覆盖这两个白格。因此，原棋盘问题无解。
如同一项优秀的交易策略，一旦越来越多人知道并复制它，其有效性就会逐渐消失。随着棋盘问题越来越流行，很多面试者只是记住了答案（毕竟答案容易记忆）。一些有创意的面试官于是设计了下面的三维版本，用来考察你的思考过程，或至少考察你能否把已有知识推广到新问题。
回到原来的三维问题：53块砖的总体积是212，小于箱子的体积216，但我们仍然可以用类似棋盘的思想证明无法全部装进去。想象将
放入任何一块
日历骰子（Calendar cubes）
题目： 你定制了两个骰子，在每个骰子的六个面上分别标记一位数字，而不是通常的1至6。你希望每天早上摆放两个骰子，让它们朝前的两个面组成当月日期。必须同时使用两个骰子，例如1日至9日必须显示为01至09；但两个骰子的左右顺序可以随意交换。两个骰子各自的六个面上应该写哪些数字？
查看解答
解答： 一个月中包含11日和22日，因此两个骰子都必须有1和2。要表示个位数日期，至少一个骰子必须有0；先在第一个骰子上放0。考虑到我们需要表示所有个位数日期，而第二个骰子不可能独自包含1至9的全部数字，因此第二个骰子也必须有0。此时已确定：
| 骰子 | 面1 | 面2 | 面3 | 面4 | 面5 | 面6 |
|---|---|---|---|---|---|---|
| 骰子一 | 1 | 2 | 0 | ? | ? | ? |
| 骰子二 | 1 | 2 | 0 | ? | ? | ? |
如果把剩余的3、4、5、6、7、8、9全部放入尚未分配的面上，问题就解决了；但剩余数字有7个，而空白面只有6个。这时需要跳出常规思路：6可以倒过来当作9使用，因为两者从不需要同时出现。于是，在一个骰子上写3、4、5，另一个骰子上写6、7、8。最终方案为：
| 骰子 | 面1 | 面2 | 面3 | 面4 | 面5 | 面6 |
|---|---|---|---|---|---|---|
| 骰子一 | 1 | 2 | 0 | 3 | 4 | 5 |
| 骰子二 | 1 | 2 | 0 | 6 | 7 | 8 |
两扇门与录用通知（Door to offer）
题目： 你面前有两扇门。一扇门通向你的工作录用通知，另一扇门通向出口。每扇门前各站着一名守卫，其中一名永远说谎，另一名永远说真话。你只能向其中一名守卫提出一个可以用“是”或“否”回答的问题。如果你想拿到录用通知，应当问什么？
查看解答
解答： 这也是一道经典脑筋急转弯（在我看来，或许已经有些过时）。一种常见的提问方式是，任选一名守卫，问他：“另一名守卫会说，你守着的这扇门通向录用通知吗？” 如果回答“是”，就选择另一扇门；如果回答“否”，就选择这名守卫身后的门。
这里只有两种情况：
- 说真话的守卫守着录用通知，说谎的守卫守着出口。
- 说真话的守卫守着出口，说谎的守卫守着录用通知。
如果直接问：“你守着的门通向录用通知吗？”在第一种情况下，两名守卫都会回答“是”；在第二种情况下，两名守卫都会回答“否”。因此，直接提问没有帮助。关键在于把两名守卫的回答嵌套进同一个问题。
在第一种情况下，若问说真话的守卫，他会如实转述说谎者的回答，而说谎者会说“否”；若问说谎的守卫，他会歪曲说真话者的回答，同样回答“否”。第二种情况下，无论问谁，得到的都是“是”。因此，回答“否”时选当前守卫身后的门，回答“是”时选另一扇门。
传递消息（Message delivery）
题目： 你需要通过快递向日内瓦的一名同事传递消息。文件已被装进一个带锁的盒子。不幸的是，快递服务并不安全，任何人在运输途中都可能打开未上锁的盒子并查看文件。你和同事都只有自己的钥匙，而盒子上的锁只能由加锁的人打开。你们要怎样在不泄露文件内容的情况下，安全地完成传递？
原书提示 ⁶： 一个盒子上可以加不止一把锁。
查看解答
解答： 如果必须把文件送到日内瓦，显然不能放在一个未上锁的盒子里。因此，首先把盒子锁上并寄给同事。同事拿到盒子后，因为没有你的钥匙，仍然无法打开。你必须设法在同事拿到文件之前移除自己的锁；这意味着盒子需要再次寄回给你。
同事可以在寄回盒子之前再加上一把他自己的锁。盒子寄回后，你移除自己的锁，再把仍然被同事的锁锁住的盒子寄给他。同事最终用自己的钥匙开锁，取出文件。
最后一颗球（Last ball）
题目： 一个袋子里有20个蓝球和14个红球。每次随机取出两个球（假设袋中球被等概率抽取）。如果两个球颜色不同，就把一个红球放回袋中；如果颜色相同，就把一个蓝球放回袋中。不断重复，直到袋子里只剩一颗球。最后一颗球是什么颜色？如果开始时有20个蓝球和13个红球呢？
原书提示 ⁷： 每一步都考虑蓝球和红球数量如何变化。
查看解答
解答： 掌握提示后，这道题很容易。设
| 取出的两颗球 | 放回之后的数量变化 |
|---|---|
| 两颗蓝球 | |
| 两颗红球 | |
| 一红一蓝 |
注意，红球数量
电灯开关（Light switches）
题目： 一个房间里有一盏灯，房间外有四个开关。最初所有开关都处于关闭状态，其中只有一个开关控制这盏灯。你可以随意开关任意开关，但只能进入房间观察一次。至少需要多少次操作，才能确定哪个开关控制电灯？
查看解答
解答： 你可能听说过经典的“三个开关、一个灯泡”问题。本题虽然略有变化，方法完全相同。只考虑灯亮与灯灭这两种状态，在一次入室观察时最多区分两种情况。若灯泡具有余热，即使灯已经熄灭，我们还可以区分“热”和“冷”。于是可以组合出四种状态。
同时打开开关1和2，等待一段时间；然后关闭开关2，打开开关3，并迅速进入房间观察灯泡：
- 灯亮且热：控制灯泡的是开关1。
- 灯亮但不热：控制灯泡的是开关3。
- 灯灭但热：控制灯泡的是开关2。
- 灯灭且冷：控制灯泡的是开关4。
量化从业者的薪水（Quant salary）
题目： 八名来自不同银行的量化从业者聚在一起喝酒，都很想知道这个小团体的平均薪水。然而，每个人都不愿意向别人披露自己的薪水。能否设计一个办法，让他们在不知道其他人薪水的情况下计算平均薪水？
查看解答
解答： 这是一道轻松的题目，而且有不止一种解法。一种方法是：第一名量化从业者随机选择一个数字，把它加在自己的薪水上，再把结果告诉第二人。第二人把自己的薪水加在收到的数字上，再把结果告诉第三人。如此依次传递，直到第八人把自己的薪水加进总数，并把结果传回第一人。第一人从最终总数中减去最初选取的随机数，再除以8，就得到平均薪水。
你可能会想到，这道题除了用于测试面试者的思维能力，还在实践中有所应用。例如，一个第三方数据提供商可能从一组参与机构的持仓数据中收集汇总信息，并定期将统计信息回传给参与者。大多数参与者显然不希望别人知道自己的具体持仓。假设每个基金的每个仓位都有唯一的ID，我们可以使用随机数（更准确地说，是伪随机数，因为提供商知道加在每个仓位ID上的随机数），把数据变得复杂且算法在每个仓位上都不同。数据提供商可以在分发前消除这些随机数。这样，同一个基金的不同仓位看起来就像来自不同基金，其他参与者便无法推断或重建基金的真实持仓。按照这种方法，参与方甚至可以在彼此保持匿名的同时共享市场信息。
2.4 对称性的应用（Application of Symmetry）
硬币堆（Coin piles）
题目： 你被蒙着眼睛带进一个房间，得知桌上共有1000枚硬币，其中980枚正面朝下，20枚正面朝上。请将这些硬币分成两堆，使两堆中正面朝上的硬币数量相等。你不能通过触摸辨认硬币的正反面，但可以任意翻转任意数量的硬币。
查看解答
解答： 先将1000枚硬币分成两堆，一堆有
由于看不到硬币的正反面，不能保证
就能保证两堆正面朝上的硬币一样多。具体做法是：随机选出20枚硬币作为第一堆，将这20枚全部翻面；剩余980枚为第二堆。
贴错标签的水果袋（Mislabeled bags）
题目： 有三个水果袋：一袋只有苹果，一袋只有橙子，一袋同时有苹果和橙子。每袋都贴着“苹果”“橙子”或“混合”的标签，但由于管理员的疏忽，三个标签全都贴错了。你可以从任意一个或多个袋子里拿取任意数量的水果。怎样用最少的取样次数，正确判断三个袋子各自装的水果？
查看解答
解答： 关键是利用“所有标签都贴错了”这个条件。举例来说，标记为“苹果”的袋子实际装的只能是橙子或混合水果。
从贴着“混合”标签的袋子中取出一枚水果。因为标签必然错误，这袋水果只能全是苹果或全是橙子。假设取出的是苹果，那么“混合”标签的袋子实际只装苹果。贴着“橙子”标签的袋子不可能只装橙子，也不能只装苹果（苹果已确定在前一袋），因此只能装混合水果；贴着“苹果”标签的袋子则只装橙子。
同理，如果从贴着“混合”标签的袋子中取出的是橙子，该袋就只装橙子；贴着“苹果”标签的袋子装混合水果，贴着“橙子”标签的袋子只装苹果。无论抽到哪种水果，一次取样足以确定全部标签。
原书提示 ⁸： 我第一次看到这道题时，把它当成一道文字游戏。但它实际上考察的是应聘者在逻辑推理方面对细节的注意程度。
智者（Wise men）
题目： 一位苏丹抓来了50名智者。他有一个杯子，最初倒扣放置。每过一分钟，他就随机叫来一名智者，这名智者可以把杯子翻过来（正放变倒扣，或倒扣变正放），也可以什么都不做。智者每次只能单独进入房间，不能彼此交流。苏丹规定：当所有智者都至少被叫到一次后，如果有一名智者能够正确宣布这一事实，所有人就获释；如果宣布错误，所有人都会被处死。智者们在被分别关押之前，可以共同商量策略。请设计一个让他们最终获释的策略。
查看解答
解答： 要让策略奏效，指定其中一人为发言人；他与其余49人的任务不同。发言人负责统计，其他49人行为相同，这种安排体现了对称性。
49名普通智者各自遵守同一规则：只有在自己尚未翻动过杯子、且看到杯子处于倒扣状态时，才把它翻成正放；其他时候不做任何事。 发言人则遵守相反的规则：只要看到杯子正放，就把它翻回倒扣，并将计数加一；如果已经倒扣，则不做任何事。
发言人完成第49次翻杯后，就知道其余49名智者都已经至少来过一次。因为每名普通智者最多只会把杯子从倒扣翻为正放一次，而发言人的每次计数都对应不同智者的首次翻杯；此时发言人自己当然也已经来过，因此可以安全地宣布所有人都已被叫到。
2.5 数列求和（Series Summation）
相传，著名数学家兼物理学家高斯小时候，老师让全班计算1至100的整数之和。老师离开教室前，高斯很快给出了如下方法。把数列正向和反向排列，每列中相对位置上的两项相加，都等于101：
因此
连续平方数的求和公式不那么直观：
不过，可以正确地猜测求和结果具有如下形式：
然后代入初始条件：
容易得到
破裂的钟面（Clock pieces）
题目： 一个钟表的表盘上，1至12按顺时针排列。表盘从墙上掉落，摔成了三块，并且每块上数字的总和相等。假设每块都是沿表盘连续的一段裂开的，不能包含分散在不同位置的数字。请问每块分别有哪些数字？
查看解答
解答： 利用前面的求和公式，所有数字之和为
三块的数字之和必须分别为26。有人会立即假设每块数字在钟面上连续，这样容易找出三组：
但这里容易犯的错误是：以为每块碎片上的数字都必须是顺时针连续的。实际上，钟面是一个圆，12与1相邻，而不规则的裂缝也可能把两段不相邻的数字连在同一块上。注意
找出缺失的整数（Missing integers）
题目： 从1到100这100个整数中，有98个互不相同的整数，另有2个整数缺失。怎样有效地找出这两个缺失的整数？
查看解答
解答： 设缺失的两个整数是
从而
再利用平方和公式，得到
即
由这两个方程即可求出
假币 I（Counterfeit coins I）
题目： 有10袋硬币，每袋100枚，外观完全相同。除了一袋以外，其余硬币每枚都重10克；假币袋中的硬币每枚可能重9克，也可能重11克。你有一台能直接显示精确重量的电子秤。只称一次，能否判断哪袋是假币，并确定假币的真实重量？
原书提示 ⁹： 若用一次称重确定假币袋，需要从每个袋子取出不同数量的硬币。如果从两袋中取出的数量相同，对称性会妨碍你区分这两袋。
查看解答
解答： 可以只称一次。从第1袋取1枚、第2袋取2枚，依此类推，直到从第10袋取10枚，一起放到秤上。总共取了
枚硬币。如果全是真币，总重量应该是550克。假设第
由于每袋取出的硬币数都不同，一次称重就能同时识别假币袋和假币的轻重。
玻璃球（Glass balls）
题目： 你在一栋100层的楼里，手里有两颗玻璃球。已知：从低于某个楼层
原书提示 ¹⁰： 假设采用最坏情况下最多扔
查看解答
解答： 假设我们希望最坏情况下最多扔
由此，最多
要覆盖100层，就需要
满足条件的最小整数是
2.6 抽屉原理（The Pigeon Hole Principle）
抽屉原理的基本表述是：如果鸽舍的数量少于鸽子的数量，那么至少有一个鸽舍中必须有不止一只鸽子。具体地说，若有
配对袜子（Matching socks）
题目： 你的抽屉里有2只红袜、20只黄袜和31只蓝袜。你是一名经常忙得忘记事情的麻省理工学院学生，随机从抽屉中拿出若干只袜子，想凑出一双颜色相同的袜子。假设每只袜子被抽到的概率相同，至少要取出多少只，才能保证拿到同色的一双？
查看解答
解答： 这是经典“两种颜色袜子”问题的一个变式。在只有两种颜色时，至少取3只就能保证出现同色的一双。现在有三种颜色（即三个“抽屉”），根据抽屉原理，取出
握手（Handshakes）
题目： 你应邀参加一个迎新聚会，与另外25名团队成员见面。聚会中，每个人都可能与其他人握手；有些人会彼此握手，有些人则不会。如果你不知道聚会中握手的总次数，能否肯定至少有两个人与完全相同数量的人握过手？
查看解答
解答： 聚会中共有26个人。每个人可能与0至25个人握手，共有26种看起来可能的握手次数。但“有一人握手0次”和“有一人握手25次”不能同时发生：如果有人与所有其余25人都握了手，就不可能同时有人一次也没握过手。因此，实际可能出现的握手次数最多只有25种，而人数有26个。根据抽屉原理，至少有两个人的握手次数相同。
我们以前见过吗？（Have we met before?）
题目： 证明：在任何一个六人聚会中，必定存在三个人两两认识，或者三个人两两互不认识。
查看解答
解答： 这道题乍看可能比较复杂，确实常让面试者困惑；但只要开始分析所有可能的情况，答案就很清楚。
假设你是聚会中的第六个人。另外五个人中，根据推广的抽屉原理，你至少认识其中三个人，或者至少不认识其中三个人。下面分别考虑这两种互斥且涵盖全部情况的情形。
情形一： 假设另外五个人中，至少有三个人与你相识。如果这三个人中有任意两个人彼此认识，那么他们两人加上你，就组成了三位两两认识的人；如果三个人两两都不认识，那么他们本身就构成三位两两陌生的人。
情形二： 假设另外五个人中，至少有三个人与你互不相识。如果这三个人中有任意两个人彼此也不认识，那么他们两人加上你，就组成了三位两两陌生的人；如果这三个人两两认识，他们本身就构成三位两两认识的人。
两种情况下，结论都成立。
正方形上的蚂蚁（Ants on a square）
题目： 一个边长为1的正方形上有51只蚂蚁。你有一个半径为
原书提示 ¹¹： 把大正方形分成25个较小的正方形，至少有一个小正方形内有3只蚂蚁。
原书提示 ¹²： 半径为
查看解答
解答： 为保证杯口罩住至少3只蚂蚁，把单位正方形平均划分成25个边长为
因此这样的杯口能够完全盖住任意一个小正方形，结论成立。
假币 II（Counterfeit coins II）
题目： 有5袋硬币，每袋100枚。一枚硬币的重量可能是9克、10克或11克；同一袋中的硬币重量相同，但你不知道每袋属于哪种重量。你有一台可以显示精确重量的电子秤。最少称几次，才能确定每袋硬币的重量？
原书提示 ¹³： 先简化成只有两袋硬币的问题。若一次称重就想知道两袋各属于哪种重量，最少应该从每袋中取出多少枚？
查看解答
解答： 如果五袋的问题一眼看不出解法，先从单袋开始。只取一枚硬币称重，就可以判断这一袋的种类。现在增加到两袋。如果第1袋取1枚、第2袋也取1枚，会有三种不同重量配对产生相同总重量，无法判断。如果只从第2袋取2枚，合计总重量相对每枚10克的标准值，可能在
如果从第2袋取3枚，总重量相对标准值的偏差就从
| 第2袋偏差 |
-1 | 0 | +1 |
|---|---|---|---|
| -1 | -4 | -3 | -2 |
| 0 | -1 | 0 | +1 |
| +1 | +2 | +3 | +4 |
其中
如果增加到三袋，将有
| 第3袋偏差 |
第2袋偏差 |
|||
|---|---|---|---|---|
| -1 | -1 | -13 | -12 | -11 |
| -1 | 0 | -10 | -9 | -8 |
| -1 | +1 | -7 | -6 | -5 |
| 0 | -1 | -4 | -3 | -2 |
| 0 | 0 | -1 | 0 | +1 |
| 0 | +1 | +2 | +3 | +4 |
| +1 | -1 | +5 | +6 | +7 |
| +1 | 0 | +8 | +9 | +10 |
| +1 | +1 | +11 | +12 | +13 |
依此类推，第4袋需取27枚，第5袋需取81枚。因此，分别从第1至第5袋取1、3、9、27、81枚硬币，合在一起称重一次，就能唯一确定五袋硬币各自的重量。
2.7 模运算（Modular Arithmetic）
模运算记为
囚犯问题（Prisoner problem）
题目： 100名囚犯得知他们明天有机会获释。每名囚犯都将戴上一顶红色或蓝色的帽子。帽子的颜色随机分配；戴上帽子后，每名囚犯都能看到其他99人的帽子颜色，但看不到自己的。此后囚犯不能以任何方式互相交流或试图传递暗号。监狱长会随机选择一名囚犯，让他当众猜测自己帽子的颜色；然后依次让所有人猜测。若猜对自己的帽子颜色，就能立即获释，否则会被处死。
今晚囚犯们可以共同商量策略。为了让尽可能多的人获释，他们应采用什么策略？最多能保证多少人获释？
查看解答
解答： 至少可以保证99名囚犯获释。
关键在于，第一位被点名的囚犯可以看到其他人的帽子，因此他可以通过自己的回答传达这99人中红帽子数量的奇偶性。让他按如下约定发言：如果看到的99顶帽子中红帽子数为奇数，就回答“红色”；如果是偶数，就回答“蓝色”。第一人自己的猜测可能正确，也可能错误；但后面的囚犯只要听到这个回答，就能知道第一人看到的99顶帽子中红帽子数的奇偶性。
第二名囚犯看到其余人的帽子，并且知道第一人的回答所编码的奇偶性，因此可以推断自己帽子的颜色。第三名囚犯还能利用第二人的正确回答和其他人的帽子颜色，依次进行推断。以此类推，除第一人以外，后面的99人都能准确判断自己的帽子颜色。
如果帽子不止两种颜色，而是红、蓝、白三种，最优策略又是什么？最多能保证多少人获释？
答案仍然是至少99人。不同之处在于，第一名囚犯的猜测正确的概率现在只有
例如，如果第一人说“红色”（编码0），后面的某名囚犯计算其余98人的编码总和得到
每个可能的余数都唯一对应一种颜色，因而能够确定
原书提示 ¹⁴： 第一名囚犯可以看到其他99名囚犯的红蓝帽子数，并用自己的猜测把红帽子数量的奇偶性告诉他们。
原书提示 ¹⁵： 如果一共有
被9整除（Division by 9）
题目： 给定一个任意整数，推导一个判断它能否被9整除的规则，并证明这个规则。
查看解答
解答： 希望你还能记得学校里学过的规则：把整数的各位数字相加，如果数字之和能被9整除，那么原整数就能被9整除；否则，原整数不能被9整除。但为什么如此？
设原整数为
它的各位数字之和为
令
由于对所有正整数
（同样可以证明：整数
变色龙的颜色（Chameleon colors）
题目： 一个偏远岛屿上有三种变色龙，分别有13只红色、15只绿色和17只蓝色。每当两只颜色不同的变色龙相遇，它们都会变成第三种颜色。例如，一只绿色和一只红色变色龙相遇，就都会变成蓝色。是否有可能让所有变色龙最终变成同一种颜色？为什么？
原书提示 ¹⁶： 考虑三种颜色的数量分别模3后的余数。
查看解答
解答： 不可能。这个结论有不止一种证明方法，这里讨论两种。
方法一： 由于13、15和17都比较大，可以先把问题简化。每次相遇使两种颜色各减少1、第三种颜色增加2，所以如果一组数量
实际上，状态
方法二： 更直接、更根本的方法是注意到：若要所有变色龙颜色相同，那么在某个中间状态必定有两种颜色的数量相同。例如，想象变色龙只差一次相遇就全部同色，此时的数量组合必须形如
三者模3的余数分别为1、0、2。当两只不同颜色的变色龙相遇时，两种颜色的数量各减1，第三种颜色的数量加2；在模3意义下，这三种数量的余数同时减1，所以它们永远两两不同。
因此，不可能出现两种颜色的数量模3相同的情形，自然也不可能出现终态中两种颜色都为0的情况。更直观地说，要让所有变色龙都成为同一种颜色，在某个阶段必须出现两种颜色的数量相同；而上述不变量排除了这种可能性。
2.8 数学归纳法（Math Induction）
归纳法是数学中最有力、最常用的证明方法之一，尤其适用于离散数学。许多问题都可以通过数学归纳法证明。一般地，要使用归纳法证明一个命题，需要：
- 明确需要证明的命题，并定义适当的谓词
。 - 证明基础情形
，或从其他最小的起始整数开始。 - 证明对每一个整数
，如果 成立，那么 也成立。对于强归纳法，也可以在证明 时共同使用 。
多数时候，真正的难点并不在归纳步骤，而在于如何把问题整理成合适的形式，以及如何提出一个合理的猜想
拆分硬币（Coin split problem）
题目： 有1000枚硬币，把它们分成两堆，并统计每堆硬币的数量。若第一堆有
查看解答
解答： 设
先验证基础情形，再用归纳法证明这一公式对所有
命题： 对于
已经验证
因此，命题对
原书提示 ¹⁷：
巧克力板（Chocolate bar problem）
题目： 一块巧克力有6行、8列，共48个
查看解答
解答： 设巧克力的行数为
若先把有
沿竖直方向拆分时同理。因此，不管如何安排拆分顺序，将
虽然数学归纳法是这道题的标准解法，但还有一个更直接的办法：观察每掰一次，巧克力块数总会增加1。开始时只有1块，最终要有
环形赛道（Race track）
题目： 在一条单向环形赛道上，随机放置了
原书提示 ¹⁸： 从
查看解答
解答： 如果一开始不知道怎么入手，就再次考虑最简单的情况
当
必然至少有一个罐满足
因此至少存在一处
因此，结论对
也有一种不同的解法。设想你开着车绕完整条赛道，并在每次经过汽油罐时收集汽油；在这一圈中，记录每次刚经过汽油罐时汽油的累计净余量。对应于全程累计净余量最小的那个位置，可以用来构造所需的起点。更形象地说，如果开始时没有汽油，从某个使累计净余量达到最小值的位置出发，就不会在后续行驶中遇到负油量。原书建议：如果这个理由并不显然，不妨自己再花些时间推敲。
2.9 反证法（Proof by Contradiction）
在反证法中，我们先假设要证明的命题是假的，然后推导出逻辑矛盾或荒谬的结果。由此可以断定：原命题必定为真。
无理数（Irrational number）
题目： 能否证明
查看解答
解答： 这是一个经典的反证法例子。假设
并且不妨假设
于是
因此
彩虹帽子（Rainbow hats）
题目： 七名囚犯得知他们明天有机会获释。行刑者会给每人戴上一顶帽子，颜色为彩虹的七种颜色之一，具体颜色完全由行刑者决定。每名囚犯都可以看到其他六人的帽子颜色，但看不到自己的；囚犯之间不能以任何形式交流，否则将立即被处死。然后，每个人都必须写下自己帽子颜色的猜测。如果至少一人猜对，全体囚犯立即获释；如果没有任何人猜对，则全体被处死。
这七名囚犯能否事先商量出一种策略，保证他们全部获释？
原书提示 ¹⁹： 将彩虹的七种颜色编码为0至6，并用
查看解答
解答： 这道题通常被认为比前面模运算一节中的囚犯问题更难。在前一题中，后面的囚犯能够听到前面人的回答；而这道题不允许囚犯之间以任何方式交流。尽管如此，解决它的关键仍然是模运算，在想到这一点后，问题也就容易理解了。
把七种颜色编码为0、1、2、3、4、5、6，并且也把七名囚犯分别编号为0至6。第
其中
按照这种策略，可以保证至少有一名囚犯猜对。事实上，设七个人真正的帽子编码之和模7的余数为
那么编号为
也可以用反证法证明这一结论。如果所有囚犯都猜错，即对每个
掌握状态与复习
关掉资料独立完成后记 A；提示后完成记 B；需要重学记 C。
记录尽量保存在当前浏览器，建议定期导出备份。