一只猩猩离家 50 米, 身边有 100 根香蕉. 如果猩猩每次最多携带 50 根香蕉, 且每移动一米都消耗一根香蕉, 问猩猩最多能把多少根香蕉带到家?

我们的方案如下: 第一步, 让猩猩携带 50 根香蕉前进 x 米, 放下尽可能多的香蕉后原路返回. 依题意, 最多在 x 米处放 50-2x 根香蕉.
第二步, 让猩猩携带剩下的 50 根香蕉, 连同在 `x` 米处暂存的香蕉一起带回家. 这一段路共消耗 50 根香蕉, 所以带回家的香蕉有 50-2x 根. 注意在 x 米处猩猩携带的香蕉不能超过 50 根, 所以 (50-2x) + (50-x) ≤ 50, 令 y = 50-2x, 从上式解得 y ≤ 50/3, 即 y ≤ 16.

若多面体表面只由正五边形和正六边形组成, 则五边形的个数一定是 12 (如, 正十二面体或足球).

设有 `x` 个五边形, `y` 个六边形, 又设该多面体的顶点数为 `V`, 棱数为 `E`, 面数为 `F`. 我们有 `F = x + y`, `quad 2E = 5x + 6y`. 因为正五边形和正六边形的内角均大于直角, 所以每个顶点处恰有三个面相交, 即 `2E = 3V`. 最后, 再和 Euler 公式 `V - E + F - 2 = 0` 联立, 得到 `x = 12`, `quad y = V/2 - 10`.

海盗分金 5 个海盗抢得 100 枚金币后讨论分赃. 他们抽签确定每人的排序 (1, 2, 3, 4, 5), 然后, 从 1 号开始提出分配方案 `(x_1, x_2, x_3, x_4, x_5)`, 其中 `Sigma x_i = 100`. 这方案由在场所有人 (包括提出者) 表决, 若同意的人数过半 ( 严格 > ), 就按此方案分配; 否则将提出者扔进大海喂鲨鱼. 若 1 号被扔进大海, 则由 2 号提出方案并由剩余在场的人按同样的规则表决. 依此类推. 我们假设
1. 每个海盗绝对理性, 即他们考虑的优先级都是 自己的生命 > 尽可能多的金钱 > 在生命得到保障, 并获得同样金钱的前提下, 尽可能减少同伙的数量.
2. 海盗都严格按照以上描述的规则进行分金, 且每一轮表决的结果都能顺利执行.
那么, 1 号海盗应该提出怎样的最优方案?

考虑 `n` 个海盗, `m` 枚金币的分金问题, 注意到 1 号被扔进大海后, 这个问题就转换为 `n-1` 个海盗, `m` 枚金币. 因此把所有海盗按提出方案的次序反向编号为 `p_n, p_(n-1), cdots, p_1, p_1` (p 是 pirates 的首字母). 记这时 1 号, 即 `p_n` 所提的方案为 `P(n) = (c_1, c_2, cdots, c_(n-1))`, (P 是 Proposal 的首字母, c 是 coin 的首字母) 剩下的金币就全归 `p_n`. 我们从较小的 `n` 开始考虑.
2. `n = 2` 时, 显然 `p_1` 总能否决 `p_2` 的方案并把他扔进大海. 这是 `p_2` 要极力避免的情形.
3. `n = 3` 时, 不论 `p_3` 提出什么方案, `p_2` 都要支持他. 此时 `P(3) = (0, 0)`.
4. `n = 4` 时, 除了 `p_4` 自己, 还需要两个拥护者来巩固自己的地位. 只要开出比 `P(3)` 更高的价钱, `p_1, p_2` 是乐意支持的. 此时 `P(4) = (1, 1, 0)`.
5. `n = 5` 时, 同样需要拉拢两名拥护者, `P(5) = (2, 0, 1, 0)` 或 `(0, 2, 1, 0)`

教授与三学生 教授在他的三个学生每人脑门上贴了纸条, 告诉他们, 每人的纸条上写着一个正整数, 其中一个数是另外两数之和. 这三个学生均非常聪明, 每人可以看见其他两人的数字, 但看不见自己的. 教授问第一个学生: 你能猜出自己的数吗? 答不能. 问第二个, 答不能. 问第三个, 答不能. 再问第一个, 答不能. 再问第二个, 答不能. 再问第三个, 答 144. 教授满意地笑了. 请问另外两人的数字是多少?

狗妈妈送肉

称硬币 [来自 Solara570@bilibili] `n` 枚硬币中, 有 0 或 1 枚假币. 真币的重量都相同, 而假币比真币偏重或偏轻. 如何利用一台无砝码的天平, 在最坏的情况下, 用最少的步数找出假币, 并确定它是偏轻还是偏重?

1. 给硬币编号 `1` 到 `n`, 设 `i` 号硬币的重量是 `x_i`. 每次称量后, 获得一个不等式. 比如把 `1, 2, 3` 号硬币放在左盘, `4, 5, 6` 号放在右盘, 而右盘更重的话, 就有 `x_1 + x_2 + x_3 lt x_4 + x_5 + x_6`. 由于至多有一枚假币, 而其他真币的重量都相同, 我们可以适当选取重量单位, 使得假币与真币的重量之差为 1. 只要保证天平两边硬币数目相同, 就可以将不等式统一处理为等式, 形如 `sum_(i=1)^n a_i x_i = b_i`. 其中 `a_i` 的取值是
   • `+1`: `i` 号硬币在右盘,
   • `-1`: `i` 号硬币在左盘, 或者
   • `0`: `i` 号硬币不参与本次称重.
   `b_i` 的取值是
   • `+1`: 右盘重,
   • `-1`: 左盘重,
   • `0`: 一样重.
   `m` 次称量后, 得到一个 `m` 行 `n` 列矩阵 `bm A` 和线性方程组 `bm A bm x = bm b`. 其中 `bm A = (a_(i j))`, `bm x = (x_1, cdots, x_n)^(sf T)`, `bm b = (b_1, cdots, b_m)^(sf T)`. 列向量 `bm x` 除了一个分量外, 其余分量都等于真币的重量 `c`. 由于我们假定天平两边硬币数目相同, `bm A` 的每一行系数之和等于 `0`, 从而我们可将 `bm x` 的每个分量都减去 `c`, 得到向量 `bm y`, 它的 `n-1` 个分量等于 0, 剩下的一个分量可能取值为 `1, -1, 0`.
2. 在方程 `bm A bm y = bm b` 中, `bm A` 称为称量矩阵, `bm b` 称为结果向量. 我们的目标是求出硬币与真币的偏差向量 `bm y`, 它一共可能有 `2n+1` 种情况:
   • `i` 号硬币偏重, 此时 `y_i = 1`, `bm b` 等于 `bm A` 的第 `i` 列.
   • `i` 号硬币偏连, 此时 `y_1 = -1` `bm b` 等于 `bm A` 的第 `i` 列取负.
   • 没有假币, 此时 `bm y = bm b = bb 0`.
   为了能区分所有 `2n+1` 种情况, `bm A` 必须满足:
   • 不存在相同的两列;
   • 不存在等于 `bb 0` 的列;
   • 不存在两列相加等于 `bb 0`;
   连同前面引入的约束一起:
   • 系数的可能取值是 `1, 0, -1`;
   • 每行系数和等于 `0`.
   构成了一个合适的称量矩阵应该满足的所有条件.
3. 计算可知, `bm A` 的编码空间大小为 `3^m`, 扣除掉零向量与负向量, `m` 次称量理论上最多可以从 `n = (3^m-1)//2` 枚硬币中找到假币并确定其轻重. 然而称量矩阵还应满足其它约束, 所以理论值还要更小一些. 比如, 3 次称量最多可以处理 12 枚硬币而不是 13 枚. 为找到称量矩阵, 你可以先列出所有可能的 `(3^m-1)//2` 个列向量, 丢弃掉多余的向量, 再给合适的列乘上 `-1`, 来保证每行系数和为 `0`. 下面是一个合适的称量矩阵 (不唯一):

   1 0  0 1  1 1 -1  0  0 -1 -1 -1
   0 1  0 1 -1 0  0 -1 -1 -1  1  1
   0 0 -1 0  0 1  1 -1  1 -1  1 -1
   

   于是称量方案为:
   • 第一次, 左盘放 7, 10, 11, 12, 右盘放 1, 4, 5, 6.
   • 第二次, 左盘放 5, 8, 9, 10, 右盘放 2, 4, 11, 12.
   • 第三次, 左盘放 3, 8, 10, 12, 右盘放 6, 7, 9, 11.
   如果三次称量结果分别是左边重, 右边重和天平平衡, 那么 `bm b = (-1, 1, 0)^(sf T)`, 它等于称量矩阵的第 5 列取负. 这就说明 5 号硬币偏轻.

称巧克力 一条巧克力的标准重量是 30 g, 每盒有 12 条巧克力. 现在生产了 10 盒巧克力, 已知其中一盒的每条巧克力是 31 g, 而其它 9 盒符合标准. 只允许使用电子秤称一次, 问如何找出这盒超重的巧克力?

和先生与积先生

能放入 10 枚硬币的正方形的最小边长?