✍️ 八股文 @ 智力题

其实互联网招聘中，有一类型考察是考察你的临场反应速度，比如脑筋急转弯这种智力题或者情景题，比如很知名的腾讯赛马问题。

1. 三人三鬼过桥

有三个人跟三个鬼要过河，河上没桥只有条小船，然后船一次只能渡一个人和一个鬼，或者两个鬼或者两个人，无论在哪边岸上，只有是人比鬼少的情况下（如两鬼一人，三鬼两人，三鬼一人）人会被鬼吃，然而船又一定需要人或鬼操作才能航行（要有人或鬼划船），问如何安全的把三人三鬼渡过河对岸?

参考回答

先两鬼过去。在一鬼回来。对面有一鬼。这边有三人两鬼。
再两鬼过去。在一鬼回来。对面有两鬼。这边有三人一鬼。
再两人过去。一人一鬼回来。对面一人一鬼。这边两人两鬼。
最后两人过去。一鬼回来。对面三人。这边三鬼。
剩下的就三个鬼二个过去一个回来在接另外个就OK了。

2. 赛马找最快的马匹（Tencent）

一般有这么几种问法：

25 匹马 5 条跑道找最快的 3 匹马，需要跑几次？参考回答：7 次
64 匹马 8 条跑道找最快的 4 匹马，需要跑几次？参考回答：11 次
25 匹马 5 条跑道找最快的 5 匹马，需要跑几次？参考回答：最少 8 次，最多 9 次

建议画图表来看，将问题简单化一点，将大问题化成小问题即可，同时 B 站有个讲解视频还不错。

Q1：25 匹马 5 条跑道找最快的 3 匹马，需要跑几次？

将 25 匹马分成 ABCDE 共 5 组，假设每组的排名就是 A1>A2>A3>A4>A5,用边相连，这里比赛 5 次

第 6 次，每组的第一名进行比赛，可以找出最快的马，这里假设 A1>B1>C1>D1>E1

D1，E1 肯定进不了前 3，直接排除掉

第 7 次，B1 C1 A2 B2 A3 比赛，可以找出第二，第三名

所以最少比赛需要 7 次

Q2：64 匹马 8 条跑道找最快的 4 匹马，需要跑几次？

第一步：全部马分为 8 组，每组 8 匹，每组各跑一次，然后淘汰掉每组的后四名，如下图（需要比赛 8 场）

第二步：取每组第一名进行一次比赛，然后淘汰最后四名所在组的所有马，如下图（需要比赛 1 场）

这个时候总冠军已经诞生，它就是 A1（它不需要比赛了）。

而其他可能跑得最快的三匹马只可能是下图中的黄域了（A2，A3，A4，B1，B2，B3，C1，C2，D1，共 9 匹马）

第三步：只要从上面的 9 匹马中找出跑得最快的三匹马就可以了，但是现在只要 8 个跑道，那就随机选出 8 匹马进行一次比赛吧（需要比赛一场）

第四步：上面比赛完，选出了前三名，但是 9 匹马中还有一匹马没跑呢，它可能是一个潜力股啊，那就和前三名比一比吧，这四匹马比一场，选出前三名。最后加上总冠军，跑得最快的四匹马诞生了！

最后，一共需要比赛的场次：8 + 1 + 1 + 1 = 11 场

Q3：25 匹马 5 条跑道找最快的 5 匹马，需要跑几次？

通过前 6 场决出第一名的方式不变，第 7 场才是关键，能否同时决出第 2、3 名次的马。

在上面的方法中，第 7 场比赛 [A2、B1、C1、D1、E1] 是为了决定第 2 名的马。但是在第 6 场比赛中我们已经得到 (B1>C1>D1>E1)，试问？有 B1 在的比赛，C1、D1、E1 还有可能争夺第 2 名吗？当然不可能，也就是说第 2 名只能在 A2、B1 中出现。实际上只需要 2 条跑道就可以决出第 2 名，剩下 C1、D1、E1 的 3 条跑道都只能用来凑热闹的吗？

能够优化的关键出来了，我们是否能够通过剩下的 3 个跑道来决出第 3 名呢？当然可以，我们来进一步分析第 3 名的情况？

如果 A2>B1 (即第 2 名为 A2)，那么根据第 6 场比赛中的 (B1>C1>D1>E1)。可以断定第 3 名只能在 A3 和 B1 中产生。
如果 B1>A2 (即第 2 名为 B1)，那么可以断定的第 3 名只能在 A2, B2, C1 中产生。

好了，结论也出来了，只要我们把 [A2、B1、A3、B2、C1] 作为第 7 场比赛的马，那么这场比赛的第 2，3 名一定是整个 25 匹马中的第 2，3 名。

我们在这里列举出第 7 场的 2，3 名次的所有可能情况：

① 第 2 名=A2，第 3 名=A3
② 第 2 名=A2，第 3 名=B1
③ 第 2 名=B1，第 3 名=A2
④ 第 2 名=B1，第 3 名=B2
⑤ 第 2 名=B1，第 3 名=C1

第 8 场比赛很复杂，我们要根据第 7 场的所有可能的比赛情况进行分析。

① 第 2 名=A2，第 3 名=A3。那么此种情况下第 4 名只能在 A4 和 B1 中产生。

如果第 4 名=A4，那么第 5 名只能在 A5、B1 中产生。
如果第 4 名=B1，那么第 5 名只能在 A4、B2、C1 中产生。
不管结果如何，此种情况下，第 4、5 名都可以在第 8 场比赛中决出。其中比赛马匹为 [A4、A5、B1、B2、C1]。

② 第 2 名=A2，第 3 名=B1。那么此种情况下第 4 名只能在 A3、B2、C1 中产生。

如果第 4 名=A3，那么第 5 名只能在 A4、B2、C1 中产生。
如果第 4 名=B2，那么第 5 名只能在 A3、B3、C1 中产生。
如果第 4 名=C1，那么第 5 名只能在 A3、B2、C2、D1 中产生。
那么，第 4、5 名需要在马匹 [A3、B2、B3、C1、A4、C2、D1] 七匹马中产生，则必须比赛两场才行，也就是到第 9 场角逐出全部的前 5 名。

③ 第 2 名=B1，第 3 名=A2。那么此种情况下第 4 名只能在 A3、B2、C1 中产生。

情况和 ② 一样，必须角逐第 9 场

④ 第 2 名=B1，第 3 名=B2。那么此种情况下第 4 名只能在 A2、B3、C1 中产生。

如果第 4 名=A2，那么第 5 名只能在 A3、B3、C1 中产生。
如果第 4 名=B3，那么第 5 名只能在 A2、B4、C1 中产生。
如果第 4 名=C1，那么第 5 名只能在 A2、B3、C2、D1 中产生。
那么，第 4、5 名需要在马匹 [A2、B3、B4、C1、A3、C2、D1] 七匹马中产生，则必须比赛两场才行，也就是到第 9 场角逐出全部的前 5 名。

⑤ 第 2 名=B1，第 3 名=C1。那么此种情况下第 4 名只能在 A2、B2、C2、D1 中产生。

如果第 4 名=A2，那么第 5 名只能在 A3、B2、C2、D1 中产生。
如果第 4 名=B2，那么第 5 名只能在 A2、B3、C2、D1 中产生。
如果第 4 名=C2，那么第 5 名只能在 A2、B2、C3、D1 中产生。
如果第 4 名=D1，那么第 5 名只能在 A2、B2、C2、D2、E2 中产生。
那么，第 4、5 名需要在马匹 [A2、B2、C2、D1、A3、B3、C3、D2、E1] 九匹马中产生，因此也必须比赛两场，也就是到第 9 长决出胜负。

总结：最好情况可以在第 8 场角逐出前 5 名，最差也可以在第 9 场搞定。

3. 给定随机函数，生成别的随机数（Tencent）

基本都是小生成大：

小生成大：给定生成 1 到 7 的随机数 Rand7()，如何得到生成 1 到 10 的随机数函数 Rand10()？
大生成小：给定生成 1 到 7 的随机数 Rand7()，如何得到生成 1 到 5 的随机数函数 Rand5()？

1️⃣ 如果是大生成小的就比较容易，比如 Rand7() 生成 Rand5()，直接取前 5 个值即可。

2️⃣ 如果是小生成大的，我们可以先构造一个大于 7 的随机数生成函数。记住以下式子：
$$
RandNN=(RandN()-1)*N+RandN()
$$
以上式子是「等概率」生成 $1$ 到 $N^2$ 之间的随机数，等概率很重要。

式子以看作是在数轴上撒豆子：

$N$ 是跨度/步长，是 RandN() 生成的数的范围长度
RandN() - 1 的目的是生成 $0$ 到 $N-1$ 的数，是跳数
后面 + RandN() 的目的是填满中间的空隙

比如 Rand49 = (Rand7() - 1) * 7 + Rand7() 可以等概率生成 1～49 之间的随机数，然后大生成小的话只需要取 1～40 (4 * 10) 之间的数字。代码如下：

LeetCode 原题：470. 用 Rand7() 实现 Rand10()

// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        while (true) {
            int v = (rand7() - 1) * 7 + rand7(); // equal prob [1 ~ 49]
            if (v >= 1 && v <= 40)
                return v % 10 + 1;
        }
    }
};

4. 砝码称轻重，找出最轻的

其实这都是一类题，这里列举几个经典的：

Q1：有一个天平，九个砝码，其中一个砝码比另八个要轻一些，问至少要用天平称几次才能将轻的那个找出来？

A1：至少 2 次。第一次，一边 3 个，哪边轻就在哪边，一样重就是剩余的 3 个；第二次，一边 1 个，哪边轻就是哪个，一样重就是剩余的那个；至少称 2 次．

Q2：十组砝码每组十个，每个砝码都是 10g 重，但是现在其中有一组砝码每个都只有 9g 重，现有一个能显示克数的秤，最少称几次能找到轻的那组？

A2：至少 1 次。将砝码分组 1~10，第一组拿一个，第二组拿两个以此类推。。第十组拿十个放到秤上称出克数 x，则 y = 550 - x，第 y 组就是轻的那组。

5. 利用空瓶换饮料，最多喝几瓶

Q：1000 瓶饮料，3 个空瓶子能够换 1 瓶饮料，问最多能喝几瓶？

思路 1

拿走 3 瓶，换回 1 瓶，相当于减少 2 瓶。

但是最后剩下 4 瓶的时候例外，这时只能换 1 瓶！

所以我们计算 1000 减 2 能减多少次，直到剩下 4（1000-4=996，996/2=498），所以 1000 减 2 能减 498 次直到剩下 4 瓶，最后剩下的 4 瓶还可以换一瓶。

所以总共是 1000+498+1=1499 瓶。

思路 2 —— 动态规划

3 个瓶子时将发生一次交换，因此前 3 个视为特殊情况
之后每增加 2 个瓶子又可以再换 1 瓶
即 dp[i] = dp[i - 2] + 2 + 1：增加 2 瓶饮料可以再换 1 瓶饮料

int dp(int n) {
    vector<int> f(n + 1);
    f[0] = 0;
    f[1] = 1;
    f[2] = 2;
    for(int i = 3; i <= n; i++) {
        f[i] = f[i - 2] + 2 + 1;
    }
    return f[n];
}

6. 毒药毒白鼠，找出哪个瓶子中是毒药

有 1000 个一模一样的瓶子，其中有 999 瓶是普通的水，有 1 瓶是毒药。任何喝下毒药的生命都会在一星期之后死亡。现在你只有 10 只小白鼠和 1 个星期的时间，如何检验出哪个瓶子有毒药？

参考答案

涉及位运算思想，首先一共有 1000 瓶，2 的 10 次方是 1024，刚好大于 1000，也就是说，1000 瓶药品可以使用 10 位二进制数就可以表示。从第一个开始：

第 1 瓶： 00 0000 0001
第 2 瓶： 00 0000 0010
第 3 瓶： 00 0000 0011
…
第 999 瓶： 11 1111 0010
第 1000 瓶： 11 1111 0011

需要十只老鼠，如果按顺序编号，ABCDEFGHIJ 分别代表从低位到高位每一个位。每只老鼠对应一个二进制位，如果该位上的数字为 1，则给老鼠喝瓶里的药。

观察，若死亡的老鼠编号为：ACFGJ，一共死去五只老鼠，则对应的编号为 10 0110 0101，则有毒的药品为该编号的药品，转为十进制数为：613 号。

类似问题还有：8 瓶酒一瓶有毒，用小老鼠测试。每次测试结果 8 小时后才会得出，而你只有 8 个小时的时间。最少需要（）老鼠测试？
A、2
B、3
C、4
D、6

答案：$8 = 2^3$，所以选 B

7. 利用烧绳子计算时间

现有若干不均匀的绳子，烧完这根绳子需要一个小时，问如何准确计时 15 分钟，30 分钟，45 分钟，75 分钟 …

15 分钟：对折之后两头烧（如果不能对折，那就参考 45 分钟的解法）

30 分钟：两头烧

45 分钟：准备两根绳子，一根两头烧，一根一头烧，同时进行，两头烧完过了 30 分钟，立即将另一根的另一头点燃，等烧完又过了 15 分钟，加起来 45 分钟

75 分钟：30 + 45

…

8. 在 24 小时内时针、分针、秒针可以重合几次

⚠️ 前提是模拟最真实的时钟走法（2 次），而非只会停留在整数（22 次）

❌ 错误答案：24 小时中时针走 2 圈，而分针走 24 圈，时针和分针重合 24-2=22 次，而只要时针和分针重合，秒针一定有机会重合，所以总共重合 22 次。

✅ 正确答案：在 24 小时内（不包含 24 点），也就只有两次重合，分别为 0 点和 12 点。

时针和分针重合的时候，秒针根本就不在重合的地方，而是在其他地方，以下是数学推导：

9. 100 个囚犯猜帽子颜色

一百个囚犯站成一纵列，每人头上随机带上黑色或白色的帽子，每个人都不知道自己帽子的颜色，但是能看见自己前面所有人帽子的颜色．然后从最后一个囚犯开始，每人只能用同一种声调和音量说一个字：”黑”或”白”，如果说中了自己帽子的颜色，就存活，说错了就拉出去斩了，说的参考回答所有囚犯都能听见。是否说对，其他囚犯不知道。在这之前，所有囚犯可以聚在一起商量策略，问如果囚犯都足够聪明而且反应足够快，100 个人最大存活人数是多少？

如果增加限制条件，每个囚犯只能看见前面一个人帽子颜色：那么方法 (3) 就失效了，只能用方法 (2)，即存活 50 人。

(1) 所有人凭运气乱猜 [50]

最坏情况下所有人都猜错，平均有 50 人猜对。

(2) 一半人凭运气 [75]

很显然，坐在最后面的囚犯是不可能保证自己猜对的，他猜黑猜白都只有一半的几率猜对，似乎没什么区别；但囚犯可以事先约定好一种暗号，即最后一个囚犯猜黑表示什么意思，猜白表示什么意思。比如，最后一个囚犯可以猜测和他前面的囚犯的帽子一样的颜色，这就相当于用他的猜测告诉了他前面那个囚犯该猜什么，于是坐倒数第二的囚犯可以保证被释放；此时，坐在倒数第三个位置上的囚犯面对与刚才坐最后的囚犯相同的处境，他同样可以用他的猜测提示出他前面那个人的帽子颜色。

相当于 50 人（偶数索引位置）给前一个报点，保证活 50 个（奇数索引位置），这样可以保证至少 50 个人猜对，平均情况则有 75 个人猜对。但这不是最佳的策略。

(3) 最佳策略 [99]

最佳策略可以保证，除了坐在最后面的囚犯以外，其余 99 个囚犯都能猜对。

最后的囚犯他完全可以透露出与全局相关的一些信息，因此以后所有的人都可以用这条信息：

比如，他可以数一数他前面 99 个人一共有多少顶白帽子，并约定他猜“黑”表示他前面共有偶数顶白帽，他猜“白”表示他前面共有奇数顶白帽。
坐倒数第二的那个人也数一数他前面 98 个人的白帽子个数：如果他数出来的个数与先前透露出的个数一奇一偶，则他自己肯定戴的是白帽子；如果他数出来的和先前透露的结果奇偶性相同，则他自己戴的肯定是黑帽子。
这样，坐倒数第二的保证可以猜对了。那接下来咋办呢？不要忘了，其他囚犯能听到刚才那人猜的是什么，并且知道他的猜测保证是对的。这相当于每个人：
- 不仅能看到坐他前面的所有人的帽子颜色
- 还知道他背后那些人的帽子颜色
- 结合最初的那个奇偶性信息
接下来的每一个人都可以猜出自己脑袋上的帽子颜色。这样下去，至少 99 个囚犯可以保证被释放。这种策略显然是最佳的，不可能再有什么策略能保证所有人都被释放，因为至少坐最后的那个人不可能保证自己猜对。

总结：等价于最后一个囚犯报全局信息，往前每一个囚犯根据全局信息、自己数得到的信息、背后那些囚犯的信息，这三条信息可以保证自己一定猜对。

10. 小猴子搬香蕉

一个小猴子边上有 100 根香蕉，它要走过 50 米才能到家，每次它最多搬 50 根香蕉，多了就被压死了，它每走 1 米就要吃掉一根，请问它最多能把多少根香蕉搬到家里？

提示：他可以把香蕉放下往返的走，但是必须保证它每走一米都能有香蕉吃。也可以走到 n 米时，放下一些香蕉，拿着 n 根香蕉走回去重新搬 50 根。

参考回答：这种试题通常有一个迷惑点，让人看不懂题目的意图。此题迷惑点在于

走一米吃一根香蕉，一共走 50 米，那不是把 50 根香蕉吃完了吗？
如果要回去搬另外 50 根香蕉，则往回走的时候也要吃香蕉，这样每走一米需要吃掉三根香蕉，走 50 米岂不是需要 150 根香蕉？

其实不然，本题关键点在于：猴子搬箱子的过程其实分为两个阶段：

第一阶段：来回搬，当香蕉数目大于 50 根时，猴子每搬一米需要吃掉三根香蕉。
第二阶段：香蕉数 <= 50，直接搬回去。每走一米吃掉 1 根。

我们分析第一阶段：假如把 100 根香蕉分为两箱。一箱 50 根。

第一步，把 A 箱搬一米，吃一根。
第二步，往回走一米，吃一根。
第三步，把 B 箱搬一米，吃一根。

这样，把所有香蕉搬走一米需要吃掉三根香蕉。

这样走到第几米的时候，香蕉数刚好小于 50 呢？

$100-(n*3)<50\ &&\ 100-((n-1)*3)>50$，n 取整数只能是 17。

走到 16 米的时候，吃掉 48 根香蕉，剩 52 根香蕉。

16 这步很有意思，它可以直接搬 50 往前走：50 - (50 -16) = 16 根

也可以再来回搬一次（即 17 这种），结果都是一样的。

到 17 米的时候，猴子还有 49 根香蕉。这时猴子就轻松啦，直接背着 49 根走就行，把剩下的 50 - 17 = 33 米走完，还剩 49 - 33 = 16 根香蕉。

11. 高楼扔鸡蛋（经典）

有 2 个鸡蛋，从 100 层楼上往下扔，以此来测试鸡蛋的硬度。比如鸡蛋在第 9 层没有摔碎，在第 10 层摔碎了，那么鸡蛋不会摔碎的临界点就是 9 层。

问：如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？

首先要说明的是这道题你要是一上来就说出正确参考回答，那说明你的智商不是超过 160 就是你做过这题。

所以建议你循序渐进的回答，一上来就说最优解可能结果不会让面试官满意。

(1) 暴力法

按楼层顺序逐层扔，但是在最坏情况下，这个方法需要扔 100 次。

(2) 二分法

类似于二分查找的方法，这个方法在最坏情况下，需要尝试 50 次。

(3) 均匀法

如何让第一枚鸡蛋和第二枚鸡蛋的尝试次数尽可能均衡呢？

只需对 100 做一个平方根运算，$\sqrt{100}=10$。

因此，尝试每 10 层扔一次：

第一次从第 10 层扔
第二次从第 20 层扔
…
第九次从第 90 层扔
第十次从第 100 层扔

这样最好的情况是第 10 层碎掉，尝试次数为 1 + 9 = 10 次；

最坏的情况是在第 100 层碎掉，尝试次数为 10 + 9 = 19 次。

优化点

可以从 15 层开始扔，接下来是 25、35、…、95，这样最坏情况是在第 95 层碎掉，尝试次数为 9 + 9 = 18 次。

(4) 最优解法

我们需要一种策略，使得无论临界楼层在哪，最坏情况下的尝试次数都相同。这意味着我们需要平衡每次扔鸡蛋后可能的后续尝试次数。

最优解法是反向思考的经典：如果最优解法在最坏情况下需要扔 X 次，那第一次在第几层扔最好呢？

参考回答是：从 X 层扔。

反向证明：

假设最优的尝试次数的 x 次，为什么第一次扔就要选择第 x 层呢？

假设第一次扔在第 x+1 层：如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第 1 层开始一层一层扔，一直扔到第 x 层。这样一来，我们总共尝试了 x+1 次，和假设尝试 x 次相悖。由此可见，第一次扔的楼层必须小于 x+1 层。

假设第一次扔在第 x-1 层：如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第 1 层开始一层一层扔，一直扔到第 x-2 层。这样一来，我们总共尝试了 x-2+1 = x-1 次，虽然没有超出假设次数，但似乎有些过于保守。

假设第一次扔在第 x 层：如果第一个鸡蛋碎了，那么第二个鸡蛋只能从第 1 层开始一层一层扔，一直扔到第 x-1 层。这样一来，我们总共尝试了 x-1+1 = x 次，刚刚好没有超出假设次数。

因此，要想尽量楼层跨度大一些，又要保证不超过假设的尝试次数 x，那么第一次扔鸡蛋的最优选择就是第 x 层。

如何求 x ？

设最优策略下，第一次在第 x 层扔鸡蛋：

如果碎了，用第二个鸡蛋从第 1 层到第 x-1 层逐层测试，最多需要 x 次（第一次 + (x-1)次）。
如果没碎，下一步从第 x + (x-1)层扔（因为已经用了一次尝试，所以下一步减少一层来保持次数平衡）。
- 如果这次碎了，用第二个鸡蛋从第 x+1 层到第 x + (x-1) - 1 层逐层测试，最多需要 2 + (x-2) = x 次。
- 如果没碎，下一步从第 x + (x-1) + (x-2)层扔，依此类推。

这样，我们需要找到一个 x，使得 $x + (x-1) + (x-2) + … + 1 ≥ 100$。即，$x(x + 1)/2 ≥ 100$。

解这个不等式：$x² + x - 200 ≥ 0$

使用求根公式：$x = \frac{-1 ± \sqrt{1 + 800}}{2} = \frac{-1 ± \sqrt{801}}{2} ≈ \frac{-1 ± 28.3}{2}$

正根约为 13.65，所以 x 至少为 $14$。

因此，最优解在最坏情况的尝试次数是 14 次，第一次扔鸡蛋的楼层也是 14 层。

最后，让我们把第一个鸡蛋没碎的情况下，所尝试的楼层数完整列举出来：14，27， 39， 50， 60， 69， 77， 84， 90， 95， 99， 100。

12. N 只蚂蚁走树枝，问总距离或者总时间

问题：放 N 只蚂蚁在一条长度为 M 树枝上，蚂蚁与蚂蚁之间碰到就各自往反方向走，问所有蚂蚁离开树枝的总时间是多少？

这个问题看起来复杂，但有一个非常巧妙的等价转换 —— 蚂蚁相遇掉头的等效性：

当两只蚂蚁相遇并掉头时，可以认为它们互相穿过而不改变方向。
这是因为：
- 从蚂蚁个体的角度看，掉头后继续走的方向和直接穿过是一样的。
- 从整体角度看，蚂蚁的位置和离开树枝的时间不会改变。
所以可以忽略碰到往反方向走这个条件。

所以答案就很简单了，就是离开树枝时间最长的那只蚂蚁所需的时间：
$$
T=max(max(x_i),max(M-x_i))
$$

13. N 个强盗分配 M 个金币，求方案使得自己分配最多

海盗分金博弈 🏴‍☠️

5 个海盗抢到了 100 枚金币，每一颗都一样的大小和价值。他们决定这么分：

抽签决定自己的号码（1，2，3，4，5）
首先，由 1 号提出分配方案，然后大家 5 人进行表决，当半数以上的人同意时（不包括半数，这是重点），按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
如果 1 号死后，再由 2 号提出分配方案，然后大家 4 人进行表决，当且仅当半超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。
依次类推……

假设每一位海盗都足够聪明，并且利益至上，能多分一枚金币绝不少分，那么 1 号海盗该怎么分金币才能使自己分到最多的金币呢？

思路

从后向前推，如果 1 至 3 号强盗都喂了鲨鱼，只剩 4 号和 5 号的话，5 号一定投反对票让 4 号喂鲨鱼，以独吞全部金币。所以，4 号惟有支持 3 号才能保命。

3 号知道这一点，就会提出“100，0，0”的分配方案，对 4 号、5 号一毛不拔而将全部金币归为已有，因为他知道 4 号一无所获但还是会投赞成票，再加上自己一票，他的方案即可通过。

不过，2 号推知 3 号的方案，就会提出“98，0，1，1”的方案，即放弃 3 号，而给予 4 号和 5 号各一枚金币。由于该方案对于 4 号和 5 号来说比在 3 号分配时更为有利，他们将支持他而不希望他出局而由 3 号来分配。这样，2 号将拿走 98 枚金币。

同样，2 号的方案也会被 1 号所洞悉，1 号并将提出（97，0，1，2，0）或（97，0，1，0，2）的方案，即放弃 2 号，而给 3 号一枚金币，同时给 4 号（或 5 号）2 枚金币。由于 1 号的这一方案对于 3 号和 4 号（或 5 号）来说，相比 2 号分配时更优，他们将投 1 号的赞成票，再加上 1 号自己的票，1 号的方案可获通过，97 枚金币可轻松落入囊中。这无疑是 1 号能够获取最大收益的方案了！

✅ 参考回答是：1 号强盗分给 3 号 1 枚金币，分给 4 号或 5 号强盗 2 枚，自己独得 97 枚。分配方案可写成（97，0，1，2，0）或（97，0，1，0，2）。

此题还有变种：就是只需要一半人同意即可，不需要一半人以上同意方案就可以通过，在其他条件不变的情况下，1 号该怎么分配才能获得最多的金币？

参考回答：类似的推理过程

4 号：4 号提出的方案的时候肯定是最终方案，因为不管 5 号同意不同意都能通过，所以 4 号 5 号不必担心自己被投入大海。那此时 5 号获得的金币为 0，4 号获得的金币为 100。

5 号：因为 4 号提方案的时候，自己获取的金币为 0 。所以只要 4 号之前的人分配给自己的金币大于 0 就同意该方案。

4 号：如果 3 号提的方案一定能获得通过（原因：3 号给 5 号的金币大于 0， 5 号就同意因此就能通过），那自己获得的金币就为 0，所以只要 2 号让自己获得的金币大于 0 就会同意。

3 号：因为到了自己提方案的时候可以给 5 号一金币，自己的方案就能通过，但考虑到 2 号提方案的时候给 4 号一个金币，2 号的方案就会通过，那自己获得的金币就为 0。所以只要 1 号让自己获得的金币大于 0 就会同意。

2 号：因为到了自己提方案的时候只要给 4 号一金币，就能获得通过，根本就不用顾及 3 号 5 号同意不同意，所以不管 1 号怎么提都不会同意。

1 号：2 号肯定不会同意。但只要给 3 号一块金币，5 号一块金币（因为 5 号如果不同意，那么 4 号分配的时候，他什么都拿不到）就能获得通过。

所以参考回答是 98，0，1，0，1。

类似的问题也可用类似的推理即可。

14. 火枪手决斗，谁活下来等概率大

彼此痛恨的甲、乙、丙三个枪手准备决斗。

甲枪法最好，十发八中；
乙枪法次之，十发六中；
丙枪法最差，十发四中。

如果三人同时开枪，并且每人每轮只发一枪；那么枪战后，谁活下来的机会大一些？

一般人认为甲的枪法好，活下来的可能性大一些。但合乎推理的结论是，枪法最糟糕的丙活下来的几率最大。那么我们先来分析一下各个枪手的策略。

如同田忌赛马一般，枪手甲一定要对枪手乙先。因为乙对甲的威胁要比丙对甲的威胁更大，甲应该首先干掉乙，这是甲的最佳策略。同样的道理，枪手乙的最佳策略是第一枪瞄准甲。乙一旦将甲干掉，乙和丙进行对决，乙胜算的概率自然大很多。枪手丙的最佳策略也是先对甲。乙的枪法毕竟比甲差一些，丙先把甲干掉再与乙进行对决，丙的存活概率还是要高一些。
我们根据分析来计算一下三个枪手在上述情况下的存活几率：
- 第一轮：甲射乙，乙射甲，丙射甲。
  - 甲的活率为24%（40% X 60%）
  - 乙的活率为20%（100% - 80%)
  - 丙的活率为100%（无人射丙）
- 由于丙 100％存活率，因此根据上轮甲乙存活的情况来计算三人第二轮的存活几率：
  - 情况 1：甲活乙死（24% X 80% = 19.2%）
    - 甲射丙，丙射甲：甲的活率为 60%，丙的活率为 20%
  - 情况 2：乙活甲死（20% X 76% = 15.2%）
    - 乙射丙，丙射乙：乙的活率为 60%，丙的活率为 40%
  - 情况 3：甲乙同活（24% X 20% = 4.8%）
    - 重复第一轮
  - 情况 4：甲乙同死（76% X 80% = 60.8%）
    - 枪战结束

据此来计算三人活率：

甲的活率为 (19.2% X 60%) + (4.8% X 24%) = 12.672%
乙的活率为 (15.2% X 60%) + (4.8% X 20%) = 10.08%
丙的活率为 (19.2% X 20%) + (15.2% X 40%) + (4.8% X 100%) + (60.8% X 100%) = 75.52%

通过对两轮枪战的详细概率计算，我们发现枪法最差的丙存活的几率最大，枪法较好的甲和乙的存活几率却远低于丙的存活几率。

15. 先手必胜问题

100 本书，每次能够拿 1～5 本，怎么拿能保证最后一次是你拿？

寻找每个回合固定的拿取模式，最后一次是我拿，那么上个回合最少剩下 $6(5_{max} + 1_{min})$ 本。那么只要保持每个回合结束后都剩下 6 的倍数，并且在这个回合中我拿的和对方拿的加起来为 6（这样这个回合结束后剩下的还是 6 的倍数），就必胜。

关键是第一次我必须先手拿（100 % 6 = 4）本（这不算在第一回合里面），剩下 96 本对方先手，只需我每次都维持当前回合共取 6 本即可，经过 16 回合即可获胜。

16. 掰巧克力问题或者参加辩论赛

掰巧克力问题

Q：我们有一块由 N×M 个小方块组成的巧克力。每次操作，可以选择一块当前的巧克力，然后沿着一行或一列将其掰开（即水平或垂直切割）。最少需要多少次操作，才能将所有巧克力掰成 1×1 的小块？

A：模拟题，即 $N - 1 + N * (M - 1) = (M*N - 1) 次$

辩论赛问题

Q：1000 个人参加辩论赛，1V1，输了就退出，需要安排多少场比赛？

A：999 场。

每场比赛有 2 人对决，1 人胜出，1 人被淘汰。因此，每场比赛都会淘汰 1 人。
最终要淘汰 999 人。因此，需要 999 场比赛，因为每场比赛淘汰 1 人。

本文由 Yikun Wu 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。