智力题

三人三鬼过桥

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

参考回答

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

赛马找最快的马匹（腾讯高频题）

一般有这么几种问法：

25匹马5条跑道找最快的3匹马，需要跑几次？参考回答：7

64匹马8条跑道找最快的4匹马，需要跑几次？参考回答：11

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

建议画图表来看，将问题简单化一点，将大问题化成小问题即可，同时B站有个讲解视频还不错：https://www.bilibili.com/video/BV1KJ411g78y

详细解法：

1、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次

2、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 场

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

(1) 首先将25匹马分成5组，并分别进行5场比赛之后得到的名次排列如下：

A组： [A1 A2 A3 A4 A5]

B组： [B1 B2 B3 B4 B5]

C组： [C1 C2 C3 C4 C5]

D组： [D1 D2 D3 D4 D5]

E组： [E1 E2 E3 E4 E5]

其中，每个小组最快的马为[A1、B1、C1、D1、E1]。

(2) 将[A1、B1、C1、D1、E1]进行第6场，选出第1名的马，不妨设 A1>B1>C1>D1>E1，此时第1名的马为A1。

(3) 将[A2、B1、C1、D1、E1]进行第7场，此时选择出来的必定是第2名的马，不妨假设为B1。因为这5匹马是除去A1之外每个小组当前最快的马。

(3) 进行第8场，选择[A2、B2、C1、D1、E1]角逐出第3名的马。

(4) 依次类推，第9，10场可以分别决出第4，5名

因此，依照这种竞标赛排序思想，需要10场比赛是一定可以取出前5名的。

仔细想一下，如果需要减少比赛场次，就一定需要在某一次比赛中同时决出2个名次，而且每一场比赛之后，有一些不可能进入前5名的马可以提前出局。

当然要做到这一点，就必须小心选择每一场比赛的马匹。我们在上面的方法基础上进一步思考这个问题，希望能够得到解决。

(1) 首先利用5场比赛角逐出每个小组的排名次序是绝对必要的。

(2) 第6场比赛选出第1名的马也是必不可少的。假如仍然是A1马 (A1>B1>C1>D1>E1)。那么此时我们可以得到一个重要的结论：有一些马在前6场比赛之后就决定出局的命运了（灰色）。

(3) 第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

(4) 第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场搞定。

给定随机函数，生成别的随机数

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

思路

由大的生成小的容易，比如由Rand7()生成Rand5()，所以我们先构造一个大于7的随机数生成函数。记住下面这个式子：

RandNN= N( RandN()-1 ) + RandN() ;// 生成1到N^2之间的随机数
可以看作是在数轴上撒豆子。N是跨度/步长，是RandN()生成的数的范围长度，
RandN()-1的目的是生成0到N-1的数，是跳数。后面+RandN()的目的是填满中间的空隙

比如 Rand25= 5( Rand5()-1 ) + Rand5()可以生成1到25之间的随机数。我们可以只要1到21（3*7）之间的数字，所以可以这么写

int rand7() {
    int x = Integer.MAX_VALUE;
    while (x > 21) {
        x = 5 * (rand5() - 1) + rand5();
    }
    return x % 7 + 1;
}

砝码称轻重，找出最轻的

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

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

参考回答：至少2次。

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

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

参考回答：至少1次。

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

正常情况：如果所有砝码都是 10g，那么总重量应该是：55×10=550 克55×10=550 克

轻的那组：假设第 y组是轻的那组，每个砝码只有 9g，那么总重量会比正常情况少 y 克。因此，实际称重的总重量 x 应该是：x=550−y

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

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

第一种思路

拿走3瓶，换回1瓶，相当于减少2瓶。但是最后剩下4瓶的时候例外，这时只能换1瓶。所以我们计算1000减2能减多少次，直到剩下4.（1000-4=996，996/2=498）所以1000减2能减498次直到剩下4瓶，最后剩下的4瓶还可以换一瓶，所以总共是1000+498+1=1499瓶。

第二种思路

可以考虑成dp思路

初始情况，3个瓶子时将发生一次交换，因此视为特殊情况
之后每增加两个瓶子又可以再换一瓶
即dp[i] = dp[i - 2] + (i - (i - 2)) + 1
- 由dp[i - 2]可求得dp[i]
- [(i - (i - 2))，即为当前增加的2瓶饮料（写成这样便于理解）
- 1即为增加了2个空瓶，之后又可以换一瓶饮料
- 简化为dp[i] = dp[i - 2] + 2 + 1

  public int method(int n) {
      // n为0/1/2的特殊情况省略了
      // 定义dp数组
      int[] dp = new int[n + 1];
      // 初始状态
      dp[0] = 0;
      dp[1] = 1;
      dp[2] = 2;
      for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 2] + 2 + 1;
     }
      return dp[n];
   }

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

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

参考回答

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

第一瓶： 00 0000 0001

第二瓶： 00 0000 0010

第三瓶： 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

解析：用3位2进制代表8瓶酒，如下表所示

瓶序号二进制中毒情况

第一瓶 000 全没中毒

第二瓶 001 只有第一个老鼠中毒

第三瓶 010 只有第二个老鼠中毒

第四瓶 011 第一个老鼠、第三个老鼠同时中毒

第五瓶 100 只有第三个老鼠中毒

第六瓶 101 第一个老鼠、第三个老鼠同时中毒

第七瓶 110 第二个老鼠、第三个老鼠同时中毒

第八瓶 111 三个老鼠同时中毒

其中，第一个老鼠喝下最低位为1对应的酒，第二个老鼠喝下中间位为1对应的酒，第三个老鼠喝下最高位为1对应的酒

最后将所有中毒的老鼠，对应的位次进行与操作即可以知道那瓶毒药有毒了

利用烧绳子计算时间

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

计算15分钟：对折之后两头烧(要求对折之后绑的够紧，否则看45分钟解法)

计算30分钟：两头烧

计算45分钟：两根，一根两头烧一根一头烧，两头烧完过了30分钟，立即将第二根另一头点燃，到烧完又过15分钟，加起来45分钟

计算75分钟：将30和45分钟的方式加起来就可以了

其余类似

在24小时里面时针分针秒针可以重合几次

24小时中时针走2圈，而分针走24圈，时针和分针重合24-2=22次，而只要时针和分针重合，秒针一定有机会重合，所以总共重合22次？

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

因此就只有 1 次重合，因为在 12 小时内不包含 12 点这个时间，所以在 24 小时内，也就只有两次重合，分别为 0 点和 12 点。

100个奴隶猜帽子颜色

一百个奴隶站成一纵列，每人头上随机带上黑色或白色的帽子，各人不知道自己帽子的颜色，但是能看见自己前面所有人帽子的颜色．然后从最后一个奴隶开始，每人只能用同一种声调和音量说一个字：”黑”或”白”，

如果说中了自己帽子的颜色，就存活，说错了就拉出去斩了，说的参考回答所有奴隶都能听见。是否说对，其他奴隶不知道。在这之前，所有奴隶可以聚在一起商量策略，问如果奴隶都足够聪明而且反应足够快，100个人最大存活率是多少？

参考回答：这是一道经典推理题

策略：

最后一个人：
- 最后一个人（第100个人）观察前面99个人的帽子颜色。
- 如果他看到的黑帽子数量是奇数，他就报“黑”；如果是偶数，他就报“白”。
- 这样，他报的颜色实际上是前面99个人黑帽子的奇偶性。
倒数第二个人：
- 倒数第二个人（第99个人）听到最后一个人报的颜色，并且能看到前面98个人的帽子颜色。
- 他根据最后一个人报的颜色和自己看到的黑帽子数量，判断自己帽子的颜色：
  - 如果最后一个人报的颜色与前面98个人黑帽子的奇偶性相同，他就报“白”（表示自己头上是白帽子）。
  - 如果不同，他就报“黑”（表示自己头上是黑帽子）。
倒数第三个人及以后：
- 每个人根据前面的人报的颜色和自己看到的黑帽子数量，判断自己帽子的颜色。
- 具体来说，每个人记住前面99个人黑帽子的奇偶性（初始值由最后一个人提供），并且每次听到“黑”时，黑帽子的奇偶性改变一次。
- 如果自己看到的黑帽子数量与记住的奇偶性相同，就报“白”；如果不同，就报“黑”。

推理过程：

最后一个人：
- 他报的颜色是前面99个人黑帽子的奇偶性。
- 他有50%的概率说对，50%的概率说错。
倒数第二个人：
- 他根据最后一个人报的颜色和自己看到的黑帽子数量，判断自己帽子的颜色。
- 他100%能说对自己帽子的颜色。
倒数第三个人及以后：
- 每个人根据前面的人报的颜色和自己看到的黑帽子数量，判断自己帽子的颜色。
- 他们100%能说对自己帽子的颜色。

因此是99人能100%存活，1人50%能活

另外，此题还有变种：每个奴隶只能看见前面一个人帽子颜色又能最多存活多少人？

参考回答：增加限制条件后，上面的方法就失效了，此时只能约定偶数位奴隶说他前一个人的帽子颜色，奇数奴隶获取信息100%存活，偶数奴隶50几率存活。

小猴子搬香蕉

一个小猴子边上有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

走到16米的时候，吃掉48根香蕉，剩52根香蕉。这步很有意思，它可以直接搬50往前走，也可以再来回搬一次，但结果都是一样的。

到17米的时候，猴子还有49根香蕉。这时猴子就轻松啦，直接背着走就行。

第二阶段：走一米吃一根。

把剩下的50-17=33米走完。还剩49-33=16根香蕉。

高楼扔鸡蛋（经典问题）

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

问：如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？首先要说明的是这道题你要是一上来就说出正确参考回答，那说明你的智商不是超过160就是你做过这题。

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

暴力法

举个例子，最笨的测试方法，是什么样的呢？把其中一个鸡蛋，从第1层开始往下扔。如果在第1层没碎，换到第2层扔；如果在第2层没碎，换到第3层扔.......如果第59层没碎，换到第60层扔；如果第60层碎了，说明不会摔碎的临界点是第59层。

在最坏情况下，这个方法需要扔100次。

二分法

采用类似于二分查找的方法，把鸡蛋从一半楼层（50层）往下扔。

如果第一枚鸡蛋，在50层碎了，第二枚鸡蛋，就从第1层开始扔，一层一层增长，一直扔到第49层。

如果第一枚鸡蛋在50层没碎了，则继续使用二分法，在剩余楼层的一半（75层）往下扔......

这个方法在最坏情况下，需要尝试50次。

均匀法

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

很简单，做一个平方根运算，100的平方根是10。

因此，我们尝试每10层扔一次，第一次从10层扔，第二次从20层扔，第三次从30层......一直扔到100层。

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

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

不过，这里有一个小小的优化点，我们可以从15层开始扔，接下来从25层、35层扔......一直到95层。

这样最坏情况是在第95层碎掉，尝试次数为 9 + 9 = 18次。

最优解法

最优解法是反向思考的经典：如果最优解法在最坏情况下需要扔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-1次机会，按照上面的说法，你第二次尝试的位置必然是X+（X-1）；

以此类推我们可得：

x + (x-1) + (x-2) + ... + 1 = 100

这个方程式不难理解：左边的多项式是各次扔鸡蛋的楼层跨度之和。由于假设尝试x次，所以这个多项式共有x项。右边是总的楼层数100。

下面我们来解这个方程：

x + (x-1) + (x-2) + ... + 1 = 100 转化为 (x+1)*x/2 = 100

最终x向上取整，得到 x = 14

因此，最优解在最坏情况的尝试次数是14次，第一次扔鸡蛋的楼层也是14层。最后，让我们把第一个鸡蛋没碎的情况下，所尝试的楼层数完整列举出来：

14，27， 39， 50， 60， 69， 77， 84， 90， 95， 99， 100

举个例子验证下：假如鸡蛋不会碎的临界点是65层，那么第一个鸡蛋扔出的楼层是14，27，50，60，69。这时候啪的一声碎了。第二个鸡蛋继续，从61层开始，61，62，63，64，65，66，啪的一声碎了。因此得到不会碎的临界点65层，总尝试次数是 6 + 6 = 12 < 14 。

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

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

参考回答：这个其实就一个诀窍：蚂蚁相碰就往反方向走，可以直接看做没有发生任何事：大家都相当于独立的

问题分析：

初始条件：
- 树枝长度为 M。
- 有 N 只蚂蚁，每只蚂蚁的初始位置不同。
蚂蚁行为：
- 每只蚂蚁以相同的速度移动。
- 当两只蚂蚁相碰时，它们会立即反方向行走。

关键思路：

等效性：
- 当两只蚂蚁相碰时，它们反方向行走的行为可以等效为两只蚂蚁直接穿过对方继续前行。
- 换句话说，蚂蚁相碰后反方向行走可以视为没有发生任何碰撞，每只蚂蚁继续沿着原来的方向行走。

简化问题：

独立行走：
- 由于蚂蚁相碰后可以视为没有发生碰撞，每只蚂蚁独立行走。
- 每只蚂蚁从初始位置开始，要么向左走，要么向右走。
最长时间：
- 每只蚂蚁从初始位置走到树枝的任一端（左端或右端）所需的时间是树枝长度 M除以蚂蚁的速度。
- 因此，所有蚂蚁中，最长时间是树枝长度 MM 除以蚂蚁的速度。

计算总距离或时间：

总距离：
- 每只蚂蚁从初始位置走到树枝的任一端的总距离是树枝长度 M。
- 因此，所有蚂蚁的总距离是 N×M。
总时间：
- 每只蚂蚁从初始位置走到树枝的任一端所需的时间是树枝长度 M除以蚂蚁的速度。
- 因此，所有蚂蚁中，最长时间是树枝长度 M 除以蚂蚁的速度。

总结：

通过将蚂蚁相碰后反方向行走的行为视为没有发生任何碰撞，问题简化为每只蚂蚁独立行走的情况。这样，计算总距离或时间就变得非常简单：

总距离：N×M
总时间：树枝长度 M 除以蚂蚁的速度

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。

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

火枪手决斗，谁活下来的概率大？

问题：彼此痛恨的甲、乙、丙三个枪手准备决斗。甲枪法最好，十发八中；乙枪法次之，十发六中；丙枪法最差，十发四中。如果三人同时开枪，并且每人每轮只发一枪；那么枪战后，谁活下来的机会大一些？

参考回答：一般人认为甲的枪法好，活下来的可能性大一些。但合乎推理的结论是，枪法最糟糕的丙活下来的几率最大。

那么我们先来分析一下各个枪手的策略。

如同田忌赛马一般，枪手甲一定要对枪手乙先。因为乙对甲的威胁要比丙对甲的威胁更大，甲应该首先干掉乙，这是甲的最佳策略。

同样的道理，枪手乙的最佳策略是第一枪瞄准甲。乙一旦将甲干掉，乙和丙进行对决，乙胜算的概率自然大很多。

枪手丙的最佳策略也是先对甲。乙的枪法毕竟比甲差一些，丙先把甲干掉再与乙进行对决，丙的存活概率还是要高一些。

我们根据分析来计算一下三个枪手在上述情况下的存活几率：

第一轮：甲射乙，乙射甲，丙射甲。

甲的活率为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%

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

先手必胜的问题

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

参考回答：寻找每个回合固定的拿取模式，最后一次是我拿，那么上个回合最少剩下6本。那么只要保持每个回合结束后都剩下6的倍数，并且在这个回合中我拿的和对方拿的加起来为6（这样这个回合结束后剩下的还是6的倍数），就必胜。

关键是第一次我必须先手拿（100%6=4）本（这不算在第一回合里面）。

问题分析：

初始条件：
- 有100本书。
- 每次可以拿1到5本书。
目标：
- 确保最后一次是你拿。

关键思路：

寻找固定模式：
- 为了确保最后一次是你拿，上一个回合结束时必须剩下6本书。
- 因此，每个回合结束后，剩下的书必须是6的倍数。
回合策略：
- 每个回合中，你和对方拿的书的总数必须是6本。
- 这样，每个回合结束后，剩下的书仍然是6的倍数。

具体策略：

初始拿取：
- 第一次拿书时，你需要先手拿书，使得剩下的书是6的倍数。
- 100本书中，100除以6的余数是4（即100 % 6 = 4）。
- 因此，第一次你需要拿4本书，这样剩下的书是96本（96是6的倍数）。
后续回合：
- 在每个回合中，你和对方拿的书的总数必须是6本。
- 例如，如果对方拿1本书，你就拿5本书；如果对方拿2本书，你就拿4本书；以此类推。
- 这样，每个回合结束后，剩下的书仍然是6的倍数。

推理过程：

第一次拿书：
- 你先拿4本书，剩下96本书。
后续回合：
- 每个回合中，你和对方拿的书的总数必须是6本。
- 例如，对方拿1本书，你就拿5本书；对方拿2本书，你就拿4本书；对方拿3本书，你就拿3本书；对方拿4本书，你就拿2本书；对方拿5本书，你就拿1本书。
确保最后一次是你拿：
- 通过上述策略，每个回合结束后，剩下的书仍然是6的倍数。
- 当剩下6本书时，对方无论拿1到5本书中的任何一本，你都可以拿剩下的书，确保最后一次是你拿。

总结：

通过第一次拿4本书，并在后续每个回合中保持你和对方拿的书的总数为6本，可以确保最后一次是你拿。这个策略的关键在于保持每个回合结束后剩下的书是6的倍数。

掰巧克力问题

掰巧克力问题：N * M块巧克力，每次掰一块的一行或一列，掰成1*1的巧克力需要多少次？

参考回答：

每次拿起一块巧克力，掰一下（无论横着还是竖着）都会变成两块。
因为所有的巧克力共有 N×M 块，所以要掰 N×M−1 次。
减去1是因为最开始的一块是不用算进去的。

推理过程：

初始状态：
- 有 N×M 块巧克力。
每次掰巧克力：
- 每次掰一块巧克力，无论横着还是竖着，都会变成两块。
- 例如，一块 2×2 的巧克力，第一次掰成两块 1×2和 1×2，再掰成 1×1 的巧克力。
总次数：
- 每次掰巧克力都会增加一块巧克力。
- 因此，从 N×M块巧克力变成 1×1的巧克力，需要 N×M−1 次。