一只猩猩离家 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. 教授满意地笑了. 请问另外两人的数字是多少?

和先生与积先生 有两个正整数 x, y, 满足 1 < x < y, 且 x+y < 100. 数学家“和先生”知道这两个数的和，数学家“积先生”知道这两个数的积，他们进行了如下对话:
积先生: 我不知道 x 和 y 分别是啥.
和先生: 我知道你不知道.
积先生: 我现在知道了.
和先生: 如果你知道了, 那我也知道了.
那么, x 和 y 各是多少?

从公共知识出发, 按步骤推理:
1. 从初始条件推出, 两数乘积必是合数, 且不是平方数. 两数和至少是 2+3=5, 至多是 49+50=99.
2. 积先生不知道, 从而 x, y 不全为素数.
3. 和先生知道积先生不知道, 由哥德巴赫猜想 (x), 两数和不能是偶数, 也不能是 p+2, 其中 p 为奇素数. 可能的两数和只有 A = {11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97}. 此外, 两数和也不能是 2p+q, 其中 p, q 是素数, q ≥ 53. 这是因为如果两个数正好是 2p 与 q, 那么积先生会发现, 乘积 2pq 不能分解为 2q 与 p, 因为 2q+p > 100. 2pq 更不能分解为 2 与 pq, 因为 2+pq > 100. 这一步直接将 ≥ 57 的两数和全部排除, 现在可能的两数和有 B = {11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53}.
4. 积先生知道了, 这说明乘积 xy 有多个非平凡分解, 但只有一个分解使得两数和属于集合 B. 特别地, 如果乘积形如 2ⁿp, 其中 n ≥ 2, p 是奇素数, 那么它只有一个分解 2ⁿ+p 满足两数和为奇数的条件. 我们先假设乘积形如 2ⁿp, 且 2ⁿ+p∈B.
5. 逐个考虑元素 b∈B, 将它写成 b = 2ⁿ+p 的形式. 如果有不止一种写法, 那么和先生在最后一步无法确定 x, y 的值, 则这个数 b 应当排除掉. 事实上

   11 = 4+7 = 8+3,
   17 = 4+13,
   23 = 4+19 = 16+7,
   27 = 4+23 = 8+19 = 16+11,
   29 = 16+13,
   35 = 4+31 = 16+19 = 32+3,
   37 = 8+29 = 32+5,
   41 = 4+37,
   47 = 4+43 = 16+31,
   51 = 4+47 = 8+43 = 32+19,
   53 = 16+37.
   

   经过排除, 剩下的可能的两数和是 C = {17, 29, 41, 53}.
6. 逐个考虑元素 c∈C, 将它写成两数和 c = x+y 的形式, 其中 1 < x < y. 并且乘积 xy 满足: 有多个非平凡分解, 但只有一个分解使得两数和属于集合 B. 如果这样的 c = x+y 有不止一种写法, 那么这个 c 应当排除掉. 事实上集合 C 中仅有 17 的写法是唯一的:

   17 = 4+13
   29 = 16+13 = 4+25 = ... // 100 分解为偶数乘奇数有 100 = 4*25 = 20*5, 但 20+5 ∉ B.
   41 = 4+37 = 16+25 = ... // 400 = 16*25 = 80*5, 但 80+5 ∉ B.
   53 = 16+37 = 32+21 = ... // 672 = 32*21 = 96*7 = 224*3, 但只有 32+21∈B.
   
   用下面的暴力程序寻找 c 的合法分解. 只有 find(17) 输出了唯一解.
   
   # 枚举 n 的非平凡分解
   def factors(n):
       res = []
       for i in range(2, int(sqrt(n))+1):
           if n % i == 0:
               res.append([i, n//i])
       return res
   
   B = [11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53]
   def find(c):
       # 枚举 x+y = c
       for y in range(c//2+1, c-1):
           x = c - y
           flag = True
           # 枚举 x*y 的分解
           for a, b in factors(x * y):
               # c 已经在 B 中, 我们跳过它
               # 一旦发现另一个分解使两数和属于 B
               # 那么乘积 xy 不是我们要找的
               if a+b != c and (a+b) in B:
                   flag = False
                   break
           # 打印合法分解
           if flag:
               print(x, y)
   

7. 结论: x = 4, y = 13.

狗妈妈送肉

称硬币 [bilibili@Solara570] `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 盒符合标准. 只允许使用电子秤称一次, 问如何找出这盒超重的巧克力?

约瑟夫问题 [葛立恒，高德纳《具体数学》] 一群人按 `1` 到 `n` 编号, 围成一圈. 从 `m` 号开始, 每 `m` 人淘汰一人, 记最后一个幸存者的编号为 `J(n, m)`.
1. 求 `J(n, 2)`;
2. 设 `m = 2`, 求倒数第二个被淘汰者的编号 `J_2(n, 2)`.
3. 求 `J(n, m)`;

1. 先设总人数为偶数. 在第一轮中, 所有编号为偶数的人被淘汰. 此时的局面与开始类似, 但人数减半, 且所有人的编号都由 `k` 变为 `2k-1`. 也就是说, `J(2n, 2) = 2 J(n, 2) - 1`. 再考虑总人数为奇数. 在第一轮中, 所有编号为偶数的人被淘汰, 接着 `1` 号也被淘汰, `3` 号排在首位. 此时的局面与开始类似, 但人数减半 (向下取整), 且所有人的编号由 `k` 变为 `2k+1`, 也就是说, `J(2n+1, 2) = 2 J(n, 2) + 1`. 下证 `J(2^n + k, 2) = 2k+1`, `quad 0 le k lt 2^n`. 首先由 `J(1, 2) = 1` 和递推 `J(2n, 2) = 2 J(n, 2) - 1` 得到: `J(2^n, 2) = 1`. 这指出人数为 `2` 的幂时 `1` 号为幸存者. 现在设人数为 `2^n+k`. 经过 `k` 次淘汰后, 排在第一位的人编号是 `2k+1`, 因此他就是最后的幸存者.
2. `J_2` 的递推关系与 `J` 完全相同, 但初值条件变为 `J_2(2, 2) = 2` 和 `J_2(3, 2) = 1`. 于是 `J_2(2 * 2^n + k, 2) = 2^n+2k+1`,
   `J_2(3 * 2^n + k, 2) = 2k+1`,
   `0 le k lt 2^n`.

---

注1: 一段模拟程序

// 返回约瑟夫游戏的 [幸存者, 倒数第二个被淘汰者]
var j = (n, m=2) => {
    a = [...Array(n).keys().map(v => v+1)]
    let i = m-1
    while (a.length > 2) {
        i %= a.length
        a.splice(i, 1)
        i += m-1
    }
    return i % 2 ? a : a.reverse()
}

j(100) // [73, 9]

注2: 考虑总人数 `N` 的二进制表示, 公式 `J(2^n + k, 2) = 2k+1`, `quad 0 le k lt 2^n` 表明, `J(N, 2)` 正好是 `N` 的向左循环移位的结果.

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

货架问题 [P&KU群群友@Lazy_Labs] 某商店只售卖一种货物. 第一天开始时刻, 店里有若干货架, 每个货架上恰有一件货物. 货物由店主分配给顾客, 顾客不能自主选择. 当某个货架上的货物卖完时, 就撤掉这个货架. 补货员会保证在第 `k` 天开始时刻, 每个未被撤掉的货架上有 `k` 件货物. 如果商店无货可卖就要关门. 现在假设你是店主, 为了保证商店不关门且每天都恰好卖出 `n` 件货物, 问第一天开始时店里至少要有多少货架?