说明：按种类汇总，难度不分先后，做了分级罗列，方便后续扩充，大家有比较有意思的题目可以在讨论区讨论。 下面有的题题解相对复杂的直接参考了网上的一些解答，而有的题解我认为并不好的也做了补充，欢迎大家批评指正！

一、质量问题

1.1 砝码称轻重

问题1.1.1、有一个天平，九个砝码，一个轻一些，用天平至少几次能找到轻的？

参考答案：至少两次；
题解：这题是已知轻重，比较简单。（1）分成三等分，两个作比较，如果两组一样重，那么第三组里面有轻的，否则可直接比出来；（2）然后在三个里面再一比一比，一样重那么第三瓶就是轻的，否则天平上谁轻就是谁。

问题1.1.2、有十组砝码每组十个，每个砝码重10g，其中一组每个只有9g，有能显示克数的秤最少几次能找到轻的那一组砝码？

参考答案：至少一次；
题解：这题明确了克数，那就不是简单的称了，需要运用一点数学知识。 1 ~ 10组依次取1 ~ 10个砝码，最终称出来为X克，第几组为Y，Y=550-X。

问题1.1.3、有十二个小球,其中一个有质量问题,不知是较重还是较轻,给你一台天平，至少需要比几次才能找出有问题的那个球，并判断轻重？

参考答案：至少三次
题解：这题不知道轻重所以难度更大一点；三等分（A,B,C），A,B先比较一次。
（1）第1次，天平平衡，那么有问题的球一定在第三组。
第2-1次，C分成3个（C1,C2,C3）和1个(C4)，然后从A,B组里面随意拿三个（这就是标准说明全是正常的），然后比较，如果一样重，那么单出的那个就是有问题的。再比第三次，判断轻重。
第2-2次，如果不平衡，那么就是有问题的在其中，同时也能判断出轻重。 第三次 ，C1和C2比，平衡，有问题的就是C3且根据第二次可以知道轻重，如果不平衡，也可以根据第二次的轻重判断出有问题的。
（2）第1次，天平不平衡，那么有问题的就在A\B中。 第二次将重的一侧标记为A1,A2,A3,A4, 轻的一侧标记B1,B2,B3,B4，第三组C，拿出A1B2B3B4与B1和C中三个比较；
第二次，如果平衡，那么问题球就在A2,A3,A4中，且重的有问题；
第三次，A2和A3比，平衡则A4有问题且重，不平衡重的那个有问题。

第二次，如果不平衡，且A1那边重（可能A1重，也可能B1轻）
第三次，A1和正常的比，平衡，那么有问题就是B1轻，不平衡，那么就是有问题的就是A1重；

第二次，如果不平衡，且B1那边重，那么有问题的就是B2B3B4中，且为轻
第三次，B2和B3比，平衡则B4有问题且轻，不平衡轻的那个有问题。
自己做的，可以参考，有更好的解法或者有问题可以交流。

二、最优解问题

2.1 利用空瓶换饮料喝

问题2.1.1、已知1000瓶饮料，3个空瓶子能够换1瓶饮料，问最多能喝几瓶？

参考答案：1499瓶；
题解1：三个空瓶能换一瓶，意味着4个为一组，每喝一组减少两个，但是最后4瓶得单独计算，（1000-4）/2 =498，最终为1000+498+1=1499.

题解2：动态规划（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。

以下是c++代码实现
  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];
   }

其中，f(n-3)+1表示喝一瓶饮料，并且使用3个空瓶子。max表示在所有可能的方案中取最大值。
初始状态为f(0) = 0，因为没有空瓶子，所以不能喝饮料。
使用动态规划的思路，可以从f(0)递推到f(1000)，最终得到最多可以喝多少瓶饮料。

以下是Python代码实现：
def max_drinks(n):
    dp = [0] * (n+1)
    for i in range(3, n+1):
        dp[i] = max(dp[i-3]+1, dp[i])
    return dp[n]

print(max_drinks(1000))

通过两种情况分析，当N为1000时，最终会留下2个瓶子，那么剩下998瓶子，每消耗2瓶可获得1瓶 ，即可兑换499瓶，所以最后可以得出共可以喝1499瓶

题解三：利用借瓶子思维
因为兑换一瓶饮料需要三个空瓶，这瓶饮料如果是找老板借来的，那么喝完后这个空瓶将会还给他，同时需要附赠给他另外两个空瓶，即每消耗手里两个空瓶就获得一瓶饮料；
但是值得注意的是，上面只是一种假设，实际情况老板是不会借给你的，因此我们至少需要保留2个空瓶，这样可以在998个瓶子剩下一个瓶子时，对其进行补足为3个空瓶，从而兑换一瓶新饮料；
此时使用998个瓶子进行上述的兑换，将获得499瓶饮料；
之前留下的两个瓶子正好无法兑换，最终获得饮料为1000 + 499 = 1499瓶。

2.2 猴子搬香蕉问题

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

参考答案：16根
题解：最终吃到50个的时候就是一往直前往前走，但是大于50个时就得分两次搬，所以就可以将整个过程分为两个阶段：
第一阶段：100个香蕉一分为二各50根，来回搬运这两组香蕉，直到小于等于50根香蕉时就可以一直往下走了；
第一步，把A组搬一米，吃一根；第二步，返回1米吃一根；第三步，搬B组一米，吃一根。 总的就是前进一米吃三根香蕉。
就可以计算出，前进多少米直到使得香蕉小于等于50根。
得出条件： 100-3n<=50 && 100-3（n-1）>= 50（网上都没有取等，我觉得应该可以取等，而且默认n为整数）
所以取的n为17满足，此时还剩33米，香蕉还剩余49根，所以最终走下去，香蕉可以剩余49-33=16根。
网上的解答是取到16开始讨论，我觉得如果按照上述条件式就不合理了，但是结果是一样的。 当n=16时，吃掉48根香蕉，还剩余34米，52根香蕉。此时选择拿着50根香蕉直接往下走还剩余16根。 还是拿50根走一米，再返回1米取剩余两根结果一致。

参考答案：17根（n不取整卡一手bug）
题解：注意题中是每走1米就吃一个香蕉，我们现在走16米的话就只消耗了16个香蕉，放下18个香蕉，带上16个香蕉返回起点再消耗16个香蕉，取剩下的50个香蕉走到16米剩下34个香蕉，这样还剩下34+18个香蕉=52，猴子没法一次拿完。
16米为中间点会多余两个香蕉，所以需要把这两个香蕉消耗掉，需要在往返途中多走2米但是不到3米的路程才行，这样有设比16米多走y米，则2=<3y<3 可得 0.66667 <=y<1，加上前面的16米即16.6667<=x<17
即只要中间点距离起点为
16.6667<=x<17
范围的距离都可以使得中间点的剩余个数为50个，拿着剩下的50个香蕉走 50 -x米，
-17 < -x <=16.6667
33 < 50-x <= 33.3333
所以最后50个香蕉走完大于33米小于34米的路程到家，只需要吃33个香蕉，还剩17个香蕉。
参考链接

2.3 高楼扔鸡蛋

问题2.3.1、有2个鸡蛋，从100层楼上往下扔，以此来测试鸡蛋的硬度。比如鸡蛋在第9层没有摔碎，在第10层摔碎了，那么鸡蛋不会摔碎的临界点就是9层。如何用最少的尝试次数，测试出鸡蛋不会摔碎的临界点？

参考答案：二分法求解应该更好
题解：
方法一、暴力法
从一楼开始扔，知道摔碎为止，最差的情况需要扔100次。复杂度O（N）

方法二、二分法
这是网上的解答，我认为二分不是这么玩的吧？
采用类似于 二分查找 的方法，把鸡蛋从一半楼层（50层）往下扔；
如果第一枚鸡蛋，在50层碎了，第二枚鸡蛋，就从第1层开始扔，一层一层增长，一直扔到第49层；
如果第一枚鸡蛋在50层没碎了，则继续使用二分法，在剩余楼层的一半（75层）往下扔；
这个方法在最坏情况下，需要尝试50次。
我的解答：
第一枚鸡蛋50楼扔，碎了区间就在1 ~ 50，没碎区间就在51 ~ 100，假设碎了，那么就在25楼扔，再依次判断。复杂度O（log2(N) + 1）

方法三、均匀法
网上的解答我觉的并不对，这里就不做贴出来了，问了一下chatgpt，一目了然：
使用均匀法（也称为线性探测法）来解决这个问题，我们可以考虑将鸡蛋从楼层1开始每隔一定的 层数（步长） 扔下去，直到它碎了。然后我们可以回到上一个没有碎的楼层，再用相同的步长往下扔鸡蛋，直到它碎了。重复这个过程，每次将步长减半，直到找到鸡蛋的临界点。
具体来说，我们可以首先选择一个步长k，从第k层楼开始扔鸡蛋。如果鸡蛋在第k层碎了，我们需要从第1层开始依次尝试k-1次来找到鸡蛋的临界点。如果鸡蛋没有在第k层碎了，我们可以将步长加上k-1，即下一次从第k+k-1层开始扔鸡蛋。如果鸡蛋在第k+k-1层碎了，我们需要从第k层到第k+k-2层依次尝试来找到鸡蛋的临界点。如果鸡蛋还没有碎，我们可以将步长再次加上k-1，即下一次从第k+k-1+k-2层开始扔鸡蛋。以此类推，直到找到鸡蛋的临界点。
假设有N层楼，步长为k，则最坏情况下的尝试次数为 (N/k) + (k-1)。我们需要找到最小的k，使得尝试次数最少。一种简单的方法是尝试不同的k值，直到找到最小尝试次数。
均匀法的时间复杂度为O(sqrt(N))，比暴力法的时间复杂度**O(N)更优秀，但比二分法的时间复杂度O(log N)**要略高。

方法四、最优解法

使用最优解法，也称为数学法，可以得到最少的尝试次数。假设有两个鸡蛋，我们需要确定鸡蛋的临界点，
即鸡蛋从该楼层开始往下掉就会碎。我们可以将问题转化为一个数学问题。

假设我们首先在第x层楼扔一个鸡蛋，如果鸡蛋碎了，那么我们需要在第1层到第x-1层之间使用第二个鸡蛋来确定鸡蛋的临界点。
如果鸡蛋没有碎，那么我们需要在第x+1层到第N层之间使用第二个鸡蛋来确定鸡蛋的临界点。
因此，最坏情况下我们需要尝试x次，其中x为一个未知的数。

我们可以通过数学分析得到最优解。
假设我们在第x层扔鸡蛋时，鸡蛋碎了。那么我们需要在第1层到第x-1层之间使用第二个鸡蛋来确定鸡蛋的临界点。
因此，我们最多需要尝试x-1次。另一方面，如果鸡蛋没有碎，那么我们需要在第x+1层到第N层之间使用第二个鸡蛋来确定鸡蛋的临界点。
如果我们在第x层扔鸡蛋后，还剩下t次尝试机会，那么我们最多可以确定的楼层数为x+t-1层。因此，我们最多需要满足以下不等式：
    x-1 + (x-2) + ... + 1 + (x+t-1) >= N
化简不等式，得到：
    x(x+1)/2 + (t-1)x >= N

通过求解上面的不等式，可以得到最少的尝试次数x，从而确定鸡蛋的临界点。
具体来说，我们可以先假设t=1，然后通过求解x(x+1)/2 + x >= N得到x的一个近似解。
然后我们可以将t逐渐增大，重新求解不等式，直到找到最小的x。

最优解法的时间复杂度为O(sqrt(2N))，比均匀法和暴力法都要更优秀，但仍然比二分法略高。

三、二进制问题

3.1 毒药问题

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

参考答案如下:
为了检验出哪个瓶子有毒药，我们可以进行如下操作：

1. 将1000个瓶子编号为从1到1000。
2. 将编号转换为二进制数，每一位表示对应位置上是否需要喂毒药。例如，瓶子1的编号为0000000001，表示只对第1只小白鼠喂毒药；瓶子2的编号为0000000010，表示只对第2只小白鼠喂毒药；瓶子3的编号为0000000011，表示对第1只和第2只小白鼠喂毒药，以此类推。
3. 将10只小白鼠编号为从1到10。
4. 将每只小白鼠对应到二进制编号上的某一位，例如，小白鼠1对应到二进制编号的第1位，小白鼠2对应到二进制编号的第2位，以此类推。
5. 将编号二进制表示中对应小白鼠的位数上为1的瓶子中取出一些瓶子，分别喂给对应的小白鼠。
6. 监测每只小白鼠是否死亡。如果有小白鼠死亡，说明对应的瓶子有毒药；否则，说明对应的瓶子是普通的水。
7. 根据小白鼠死亡的情况推断出哪个瓶子有毒药。

具体来说，首先一共有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号

注释：抖音上有些算姓氏，算数字的，很多逻辑也与此类似。

3.2 分金块问题

问题3.2.1：工人为老板打工，工作七天可以获得一块金子，工人每天可以分得一点金子，老板必须每天发金子，不能多给，也不能少给，把这个金子切两刀，就可以每天给工人发工资，请问怎么切？

参考答案如下：
切两刀将金子分成三份，1/7、2/7、4/7；
工作第一天 把1/7分给工人；
工作第二天 把2/7分给工人，并要回1/7那块金子，工人有2/7的金子；
工作第三天 把1/7给工人，工人有3/7金子；
工作第四天 把前两块金子要回，给工人4/7的金子 工人有4/7的金子；
工作第五天 把1/7分给工人 工人有5/7的金子；
工作第六天 把2/7分给工人，并要回1/7那块金子，工人有6/7的金子；
工作第七天 把1/7给工人，工人有完整的金子；
扩展：如何给工人发15天的工资？把金块分成1/15、2/15、4/15、8/15

四、赛马问题

4.1 赛马找最快的马匹

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

参考答案：7
题解：

将25匹马分成ABCDE5组，假设每组的排名就是A1>A2>A3>A4>A5,用边相连，这里比赛5次
第6次，每组的第一名进行比赛，可以找出最快的马，这里假设A1>B1>C1>D1>E1
D1，E1肯定进不了前3，直接排除掉
第7次，B1 C1 A2 B2 A3比赛，可以找出第二，第三名
所以最少比赛需要7次

问题4.1.2 64匹马8条跑道找最快的4匹马，需要跑几次？

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

第二步：取每组第一名进行一次比赛，然后淘汰最后四名所在组的所有马，如下图（需要比赛1场）这个时候总冠军已经诞生，它就是A1

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

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

第四步：上面比赛完，选出了前三名，再和没跑的那个马比一场就可以得出2 ~ 4名。
最后，一共需要比赛的场次：8 + 1 + 1 + 1 = 11 场

问题4.1.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场比赛之后就决定出局的命运了(下面加粗斜体标志出局)。

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 ]

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

五、先手必胜问题

5.1 抢 30的必胜策略

问题5.1.1 抢 30 是双人游戏，游戏规则是：第一个人喊“ 1 ”或“ 2 ”，第二个人要接着往下喊一个或两个数，然后再轮到第一个人。两人轮流进行下去，最后喊 30 的人获胜，问喊数字的最佳策略。

参考答案，尽量后喊，切喊三的倍数；
题解： 倒着看，喊 27 的人必胜。假设 A 喊了 27，B只能喊 28 或 29 ， 下个回合，A 一定可以喊30。以此类推，喊24的人必胜，即喊 3 的倍数者必胜
若双方争抢3的倍数（假设每次都是最优解），谁先喊，谁一定输

5.2 拿书问题

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

题解：如果最后一次是我拿，那么上回合最少剩下6本；
只要保持每个回合结束后都剩下6的倍数，且在这个回合中我拿的书和对方拿的书加起来为6本；第一次我必须先手拿4本(100 % 6 = 4)，这不算在第一回合内

5.3 轮流拿石子

问题5.3.1一共有N颗石子，每次最多取M颗最少取1颗，A，B轮流取，谁最后会获胜？（假设他们每次都取最优解）

简单的巴什博奕
参考答案：
假如A先取，N<M，A获胜
　　　　　 N>M，若N能被（M + 1）整除时，A失败
　　　　　　　　 若N不能被（M + 1）整除时，A获胜
题解：以A先手为例，N<M时A一次拿完（不可能给B留机会，前提就是每次取最优），不会给B留机会；
N>M时，A要想赢，必须要在自己倒数第二次取完的时候还剩下（M + 1）颗石子，这样不论B取几颗，A都获胜！因此要控制最后一轮的石子数量，分两种情况分析：
（1）N不能被（M + 1）整除，A先拿走n颗石子（使得剩下的石子数量是（M + 1）的整数倍），那么下一次B拿走k颗石子时，A就拿走（M + 1）- k颗石子。这样不论B怎么拿A总能控制剩下的石子数量是（M + 1）的整数倍，那么最后一轮一定剩下（M + 1）颗；
（2）N能被（M + 1）整除，无论A怎么拿，B可以控制剩下石子数量（M + 1）的整数倍，在最后一轮之前B拿完后还剩（M + 1）颗，A拿多少颗都是输。
同上面的5.1和5.2.

问题5.3.2 有若干堆石子，每堆石子的数量是有限的，二个人依次从这些石子堆中拿取任意的石子，至少一个（不能不取），最后一个拿光石子的人胜利。

尼姆博弈浅谈（Nim）

#include<stdio.h>
int main()
{
	int n,a=0,b;//初始化a为0为了保证不管异或谁都可以
	scanf("%d", &n);//数字个数
	while (n--)
	{
		scanf("%d", &b);
		a ^= b;//异或！！！
	}
	printf(a ? "YES\n" : "NO\n");//最后判断输出即可
	return 0;
}

六、水桶取水问题（印象中小学奥数就玩过）

6.1 取水

问题6.1.1 水资源无限，5L和3L水桶各一个，怎样取4L的水？

参考答案；
解法一：
初始时0，3（5L，3L）
交换3，0
注满3，3
倒入5，1
清空0，1
交换1，0
注满1，3

解法二；
初始时5,0（5L,3L）
倒入2,3
清空2,0
倒入0,2
注满5,2
倒入4,3

问题6.1.2

参考答案：水资源无限，5L和6L水桶各一个，怎样取3L的水？
解法一：
初始时5，0（5L，6L）
交换0，5
注满5，5
倒入4，6
清空4，0
交换0，4
注满5，4
导入3，6

解法二：
初始时0,6（5L，6L）
交换5,1
清空0,1
交换1,0
注满1,6
倒入5,2
倒掉0,2
交换2,0
注满2,6
倒入5,3

6.2 分水

6.2.1 一个装了10L水的桶，一个7L的空桶，一个3L的空桶，怎样变成2个5L？

参考答案：
初始时10，0，0（10L, 7L, 3L）
注满3，7，0
注满3，4，3
清空6，4，0
倒入6，1，3
清空9，1，0
交换9，0，1
注满2，7，1
注满2，5，3
合并5，5，0

七、计时问题

7.1 沙漏计时（类似水桶问题）

问题7.1.1 有一个能计时6分钟的小沙漏和一个能计时8分钟的大沙漏，如何计时10分钟？

参考答案；
两个沙漏同时倒置开始计时，等小沙漏漏完，大沙漏还剩2分钟，这时倒置小沙漏继续计时；
大沙漏漏完小沙漏还剩4分钟，再把大沙漏倒置继续计时；
小沙漏漏完大沙漏还剩4分钟，这时准备工作已经完毕；
等待大沙漏漏完（4分钟）+ 小沙漏（6分钟） = 10分钟

7.2 烧绳/蜡烛计时（可以两头进行）

问题7.2.1 烧一根绳子需要一个小时，现有若干条相同的绳子，问如何计时15分钟？

参考答案：
点燃绳子A的一头，同时点燃绳子B的两头； 绳子B烧完的时候绳子A还剩一半，此时点燃绳子A的另一头开始计时；15分钟绳子A烧完。

问题7.2.1 蜡烛燃烧问题：两根蜡烛，燃烧完都需要1小时，怎么确定15分钟是多久？

参考答案：
同上，点燃第一根的一端，第二根的两端，第二根烧完代表半小时后，点燃第一根另一端，烧完代表15分钟。

八、过河/过桥问题

8.1 三人三鬼过桥（狼羊过河）

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

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

8.2 限时过桥问题

问题8.2.1 在一个夜晚，同时有4人需要过一桥，一次最多只能通过两个人，且只有一只手电筒，而且每人的速度不同。A，B，C，D需要时间分别为：1，2，5，10分钟。问：在17分钟内这四个人怎么过桥？

参考答案：
总共是17分钟
第一步：A、B过花时间2分钟
第二步：B回花时间2分钟
第三步：C、D过花时间10分钟
第四步：A回花时间1分钟
第五步：A、B再过花时间2分钟

九、灯泡开关问题

9.1 判断开关对应的灯泡（一对一）

问题9.1.1在房里有三盏灯，房外有三个开关，在房外看不见房内的情况，你只能进门一次，你用什么方法来区分那个开关控制那一盏灯？

参考答案： 有脑筋急转弯的因素（考虑了一下通过二进制的方式多次开关反推，发现行不通）
打开一个开关，过10分钟后关掉开关，并打开另一个开关。进屋确认可知：
亮的灯是由第二次打开的开关控制；
摸上去发热的不发亮的灯是由第一次打开的开关控制
剩下的第三盏灯是由未操作过的开关控制

9.2 圆环灯泡（一对多）

问题9.2.1 一个圆环上有 100 个灯泡，灯泡有亮和暗两种状态。按一个灯泡的开关可以改变它和与它相邻两个灯泡的状态。设计一种算法，对于任意初始状态，使所有灯泡全亮

参考答案:
将灯泡编号 1 ~ 100
步骤一：将灯泡变为全亮或只剩一个为暗
从 1 循环到 98 ，遇到暗的则按它下一个，使之变亮。循环完毕，1 ~ 98 必然全亮。99 和 100可能为亮亮、暗亮、亮暗、暗暗四种状态
若为亮亮，皆大欢喜，满足题目要求
暗亮、亮暗，达到只剩一个为暗的状态；
若为暗暗。则按下编号 100 的灯泡，使编号 99 、100 变为亮，编号 1 的灯泡变为暗，从而达到只剩一个为暗的状态
步骤二：将灯泡变为全暗
由于灯泡环形摆放，我们指定暗的灯泡编号为 1 ，将剩下 99 个亮着的灯泡每 3 个为一组。按下每组中间的灯泡后，使得所有灯泡变为暗
步骤三：将灯泡变为全亮
将所有灯泡按一下，灯泡变为全亮;

扩展:对于 N 个灯泡的任意初始状态 ( N > 3 ) ，能否经过若干次操作使得所有灯泡全亮？
答案：N 个灯泡做分类讨论。
N = 3k+1一定可以。方法与上述步骤相同，在步骤二中可以将3k个亮的灯泡分为k组。
N = 3k+2一定可以。将上述步骤一目标状态的只剩一个为暗改成剩两个相邻为暗，其余 3 * k 个灯泡分组按即可。因为，对于任意只剩一个为暗的状态，按下该灯泡左右任意一个就可以变成剩两个相邻为暗的状态！
N = 3*k不一定。如果经过上述步骤一可以将灯泡变成全亮的状态则有解；否则，无解。（该结论有待证明）
附:
对于这道题，以下两个状态可以相互转化
全暗 <=> 全亮。全暗和全亮状态可以相互转化，方法就是将每个灯泡按一次。这样每个灯泡都被改变了 3 次状态，使得全暗变为全亮，全亮也可变为全暗。
剩一个为暗 <=> 剩两个相邻为暗。剩一个为暗时，按下该灯泡左右任意一个，就变成了剩两个相邻为暗的状态；剩两个相邻为暗时，按下第二个暗，便可变成了剩一个为暗的状态

十、博弈论游戏

10.1 圆桌放硬币

问题10.1.1 双人游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币，每次必需且只能放置一枚硬币，要求硬币完全置于桌面内（不能有一部分悬在桌子外面），并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币，谁就输了。游戏的先行者还是后行者有必胜策略？这种策略是什么？

参考答案：
先行者在桌子中心放置一枚硬币，以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样，只要后行者能放，先行者一定也有地方放。先行者必胜

规律总结：
假设圆桌上共有 n 个固定位置可以放置硬币，且两个游戏者都是聪明且理性的。我们可以用数学归纳法证明，当且仅当 n 是偶数时，先行者有必胜策略，否则后行者有必胜策略。

当 n=2 时，先行者只需要放置一个硬币，后行者无论怎样放置都会输。
当 n=4 时，先行者放置一个硬币在桌子中心，并占据了一个对称位置。此时，无论后行者怎样放置硬币，先行者都可以通过对称性来放置硬币，保持自己的优势。
当 n=6 时，先行者可以像 n=4 时那样放置硬币，并占据一个对称位置。此外，先行者还可以放置一个硬币在圆桌中心，从而占据一个更加优势的位置。这种情况下，后行者无论怎样放置硬币都会输。

通过这样的归纳法证明，我们可以得出结论：当 n 是偶数时，先行者有必胜策略，否则后行者有必胜策略。对于先行者来说，他只需要在游戏开始时先放置一个硬币在圆桌中心，然后按照一定的策略来占据对称位置，从而保持自己的优势。对于后行者来说，他需要尽可能地破坏先行者的对称性，以便获得优势。

10.2 狼吃羊问题

问题10.2.1 故事发生在某个神奇的草原：草原上有100只狼和1只羊。狼可以吃草也可以吃羊。按照常理，狼当然更喜欢吃羊。但是，如果狼吃了羊，狼就会变成羊，从而可以被其他狼追上，并吃掉。这些狼的奔跑速度各不同，但是都非常理性。假设羊不能被两只或者更多狼分吃。请问：羊会不会被狼吃？请写出推理过程。

参考答案：不会
题解：
情况1：2只狼和1只羊时，吃了羊的狼会被另一只狼吃掉，所以2只狼一只羊会稳定
情况2：3只狼和1只羊时，一只狼吃了羊后会变成情况1，所以不会被吃，则2最终会变成1
情况3：4只狼和1只羊时，一只吃了羊后会变成情况2，会被其他狼吃掉，所以情况3会稳定
…
递推可得：偶数只狼时，羊不会被吃掉；奇数只狼时，羊会被吃掉。

十一、数字问题

11.1 11223344问题

问题11.1.1 有8个数，11223344，将其排列，要求结果满足：两个1之间有一个数，两个2之间有两个数，两个3之间有三个数，两个4之间有四个数。问这个结果是多少？

参考答案：
41312432 或 23421314
位数有限，所以先排最大的4，再排3再排2

11.2 随机数问题

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

参考答案：
首先，我们可以使用Rand5()生成两个随机数，例如x和y，它们都是1到5之间的整数。接下来，我们可以用这两个随机数生成1到25之间的随机数：
rand25 = (x - 1) * 5 + (y - 1) + 1
这个公式的含义是将x和y看作是一个二维坐标系中的点，其中x的取值范围是1到5，y的取值范围也是1到5。因此，这个点可以表示为(x, y)。我们将这个点映射到一个一维的坐标系中，其中第x行有5个元素，第y列有1个元素，因此这个点在一维坐标系中的位置为(x - 1) * 5 + (y - 1) + 1。
接下来，我们需要将这个1到25之间的随机数映射到1到7之间。我们可以使用模运算来实现这个映射，具体地：
rand7 = rand25 % 7 + 1
这个公式的含义是将rand25除以7，得到一个商和一个余数。由于rand25是1到25之间的数，因此rand25除以7的商只能是1、2、3。因此，我们可以使用rand25除以7的余数来得到1到7之间的随机数。
需要注意的是，由于rand25生成的随机数是等概率的，因此rand7生成的随机数也是等概率的。这个算法的时间复杂度是O(1)。

下面是使用C语言实现生成1到7的随机数函数Rand7()的代码：

int Rand5() {
    // 生成1到5之间的随机数
}

int Rand7() {
    int rand25 = 0;
    int rand7 = 0;
    do {
        rand25 = (Rand5() - 1) * 5 + (Rand5() - 1) + 1;
        rand7 = rand25 % 7 + 1;
    } while (rand25 > 21); // 如果rand25大于21，则重新生成rand25和rand7
    return rand7;
}

十二、推理题

12.1 掰巧克力问题

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

参考答案：N * M - 1次；
题解：
不管怎么掰，每次只能把一个大块掰成两个小块，即每次掰只能增加1块巧克力； 那么将1块巧克力掰成N * M块小巧克力就需要掰N * M - 1次

12.2 辩论赛问题

问题12.2.1 1000个人参加辩论赛，1对1进行辩论，淘汰输掉的一方，问需要安排多少场比赛才能角出冠军？

参考答案：999场
题解：
每场辩论赛只能淘汰一个人，要淘汰999个人则需要安排999场比赛

12.3 秒时分针问题

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

参考答案：22次：
题解：
首先，我们可以先考虑时针和分针重合的次数。12小时内，时针和分针会重合11次。这是因为分针每小时都会迎头赶上时针，但在时针和分针都指向12的时候不算重合，所以是11次。那么在24小时内，时针和分针会重合22次。

然后，我们来看秒针与时针、分针重合的情况。由于秒针的速度远大于时针和分针，它会在很短的时间内与时针、分针重合。所以，我们可以近似认为当时针、分针重合时，秒针也会参与重合。因此，在24小时内时针、分针、秒针重合的次数大约是22次。

注意：完全重合只有两次。

12.4 蓝眼睛问题

问题描述：有个岛上住着一群人，有一天来了个游客，定了一条奇怪的规矩：所有蓝眼睛的人都必须尽快离开这个岛。每晚8点会有一个航班离岛。每个人都看得见别人眼睛的颜色，但不知道自己的（别人也不可以告知）。此外，他们不知道岛上到底有多少人是蓝眼睛的，只知道至少有一个人的眼睛是蓝色的。所有蓝眼睛的人要花几天才能离开这个岛？
参考答案：有多少个蓝眼睛的人就会花多少天。
题解；
假设有M个人，N个蓝眼睛
n=1
假设岛上所有人都是聪明的，蓝眼睛的人四处观察之后，发现没有人是蓝眼睛的。但他知道至少有一人是蓝眼睛的，于是就能推导出自己一定是蓝眼睛的。因此，他会搭乘当晚的飞机离开。
n=2
两个蓝眼睛的人看到对方，并不确定n是1还是2，但是由上一种情况，他们知道，如果n = 1，那个蓝眼睛的人第一晚就会离岛。因此，发现另一个蓝眼睛的人仍在岛上，他一定能推断出n = 2，也就意味着他自己也是蓝眼睛的。于是，两个蓝眼睛的人都会在第二晚离岛。
n>2
逐步提高n时，我们可以看出上述逻辑仍旧适用。如果n = 3，那么，这三个人会立即意识到有2到3人是蓝眼睛的。如果有两人是蓝眼睛的，那么这两人会在第二晚离岛。因此，如果过了第二晚另外两人还在岛上，每个蓝眼睛的人都能推断出n = 3，因此这三人都有蓝眼睛。他们会在第三晚离岛。
不论n为什么值，都可以套用这个模式。所以，如果有n人是蓝眼睛的，则所有蓝眼睛的人要用n晚才能离岛，且都在同一晚离开。

12.5 疯狗问题

问题描述：有50家人家，每家一条狗。有一天警察通知，50条狗当中有病狗，行为和正常狗不一样。每人只能通过观察别人家的狗来判断自己家的狗是否生病，而不能看自己家的狗，如果判断出自己家的狗病了，就必须当天一枪打死自己家的狗。结果，第一天没有枪响，第二天没有枪响，第三天开始一阵枪响，问：一共死了几条狗？
参考答案：死了3条（第 几天枪响就有几条）。
题解：从有一条不正常的狗开始，显然第一天将会听到一声枪响。这里的要点是你只需站在那条不正常狗的主人的角度考虑。有两条的话思路继续，只考虑有两条不正常狗的人，其余人无需考虑。通过第一天他们了解了对方的信息。第二天杀死自己的狗。换句话说每个人需要一天的时间证明自己的狗是正常的。有三条的话，同样只考虑那三个人，其中每一个人需要两天的时间证明自己的狗是正常的狗。

12.6 耳光问题

问题描述：一群人开舞会，每人头上都戴着一顶帽子。帽子只有黑白两种，黑的至少有一顶。每个人都能看到其他人帽子的颜色，却看不到自己的。主持人先让大家看看别人头上戴的是什么帽子，然后关灯，如果有人认为自己戴的是黑帽子，就打自己一个耳光。第一次关灯，没有声音。于是再开灯，大家再看一遍，关灯时仍然鸦雀无声。一直到第三次关灯，才有劈劈啪啪打耳光的声音响起。问有多少人戴着黑帽子？

参考答案：有三个人戴黑帽。
题解：
假设有N个人戴黑帽，当N＝1时，戴黑帽的人看见别人都为白则能肯定自己为黑。于是第一次关灯就应该有声。可以断定N＞1。对于每个戴黑帽的人来说，他能看见N-1顶黑帽，并由此假定自己为白。但等待N-1次还没有人打自己以后，每个戴黑人都能知道自己也是黑的了。所以第N次关灯就有N个人打自己。

12.7 蚂蚁问题

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

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

A蚂蚁与B蚂蚁相碰后你可以看做没有发生这次碰撞，这样无论是求时间还是距离都很简单了。

十三、概率问题

13.1 图形问题

问题13.1.1 一个圆上随机画两条弦，求相交的概率？

参考答案：1/3；
题解：
四个点确定两条线，在一个圆上取四个点； 四个点画两条线有三种情况，其中只有一种情况是相交的，故相交概率为 三分之一

注意区别一下，圆内作弦，比较专业，可做参考。
圆内作弦求相交概率

问题13.1.2 一条绳子砍两刀，能构成一个三角形的概率？

参考答案：1/4
设绳子总长为L，分成三段为：x，y，L – x – y； 其中x > 0，y > 0， L – x – y > 0，取值范围如图中蓝色区域所示；
又因为任意两边之和要大于第三边，故有如下条件： x + y > L – x – y => y > -x + L / 2； x + (L – x – y) > y => y < L / 2; y + (L – x – y) > x => x < L / 2;
该区域为图中绿色区域，占蓝色区域的 四分之一；

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

问题13.2.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%
通过对两轮枪战的详细概率计算，我们发现枪法最差的丙存活的几率最大，枪法较好的甲和乙的存活几率却远低于丙的存活几率

13.3 猜谜问题

13.3.1 100个奴隶猜帽子颜色

问题：一百个奴隶站成一纵列，每人头上随机带上黑色或白色的帽子，各人不知道自己帽子的颜色，但是能看见自己前面所有人帽子的颜色． 然后从最后一个奴隶开始，每人只能用同一种声调和音量说一个字：”黑”或”白”， 如果说中了自己帽子的颜色，就存活，说错了就拉出去斩了，说的参考回答所有奴隶都能听见。 是否说对，其他奴隶不知道。 在这之前，所有奴隶可以聚在一起商量策略，问如果奴隶都足够聪明而且反应足够快，100个人最大存活率是多少？
参考答案：
1、最后一个人如果看到奇数顶黑帽子报“黑”否则报“白”，他可能死
2、其他人记住这个值（实际是黑帽奇偶数），在此之后当再听到黑时，黑帽数量减一
3、从倒数第二人开始，就有两个信息：记住的值与看到的值，相同报“白”，不同报“黑” 99人能100%存活，1人50%能活
另外，此题还有变种：每个奴隶只能看见前面一个人帽子颜色又能最多存活多少人？ 参考回答：增加限制条件后，上面的方法就失效了， 此时只能约定偶数位奴隶说他前一个人的帽子颜色， 奇数奴隶获取信息100%存活，偶数奴隶50%几率存活