建模。一天的时间限制意味着只有一轮实验：所有品酒师今晚同时喝，明天看生死。每个人是一比特信道：活/死。要把「100 种毒酒假设」装进「\(n\) 人的生死组合」里，用知识点一的下界加构造框架。

推导。下界：\(n\) 个人的生死状态至多 \(2^{n}\) 种，要区分 100 瓶，需 \(2^{n} \ge 100\)。\(2^{6} = 64 \lt 100 \le 128 = 2^{7}\)，故 \(n \ge 7\)。构造：把瓶子编号为 0 到 99，写成 7 位二进制 \(b_{6}b_{5}\dots b_{0}\)。第 \(i\) 位品酒师喝下所有第 \(i\) 位为 1 的酒（每人约喝 50 瓶的混合样）。次日，把 7 个人的状态排成一个 7 位向量：死了记 1、活着记 0——这个向量的二进制值恰好就是毒酒的编号。例如只有第 0 位和第 6 位品酒师死了，则毒酒编号是 \(1000001_{2} = 65\) 号。若无人死亡，编号是 0（全零向量），对应 0 号瓶——所以编号必须从 0 开始，恰好把 \(2^{7} = 128\) 个输出组合中的前 100 个用满。

检验。逐一核对：不同毒酒的二进制编号不同，死者的集合必不同，因此方案无歧义；每人一比特，7 比特 \(\ge \log_{2} 100 \approx 6.64\) 比特，信息量刚好够。边界情形：全活对应 0 号酒，全死对应 127 号——127 号不在 0 到 99 范围内，所以「全死」不会出现，输出集合与假设集合一一对应。时间约束也满足：只需一个昼夜。

面试怎么讲。先报答案「7 人」，再给两段论证：「64 种生死组合装不下 100 瓶，所以 6 人不够；7 人够，因为把瓶号写成 7 位二进制、让第 \(i\) 人喝所有第 \(i\) 位是 1 的酒，死者集合的二进制就是毒酒编号。」若扩展到多轮，死亡者不能再次参加。每人最多输出“第几轮死亡”或“全程存活”，r 轮、k 人最多提供 \((r+1)^k\) 种结果，不能按 \(2^{kr}\) 计数；例如 2 人、4 轮至多区分 25 瓶。构造时还须保证各轮取样与毒发时间可区分。

先检查是否唯一。PDF 未说明缺的是哪一个和，因此不能把五个已知和中最小的直接认成 a+b；真正的最小和可能正是缺失项。题目也未保证唯一解，应返回全部满足条件的有序后排序四元组，或报告无解/不唯一。

从完整三角形恢复三个数。把四个数看成四个顶点、两两和看成六条边。只缺一条边时，至少有一个三顶点三角形的三条边全在已知数据里。枚举三个不同的观测位置，假设其值分别为 \(u=a+b,v=a+c,w=b+c\)，则 \(a=(u+v-w)/2\)、\(b=u-a\)、\(c=v-a\)。只保留正整数。第四个数 d 至少有一条与这三个数相连的已知边，枚举 \(d=s-a,s-b,s-c\)，再把候选的六个和作为多重集合核对：五个观测必须能逐一删除，且恰剩一个和。

set<array<long long, 4>> recoverFour(const vector<long long>& sums) {
    if (sums.size() != 5) throw invalid_argument("need five sums");
    set<array<long long, 4>> answers;
    // Choose an intact triangle: u=a+b, v=a+c, w=b+c.
    for (int i = 0; i < 5; ++i) for (int j = 0; j < 5; ++j)
        for (int k = 0; k < 5; ++k) {
            if (i == j || i == k || j == k) continue;
            long long twiceA = sums[i] + sums[j] - sums[k];
            if (twiceA <= 0 || twiceA % 2) continue;
            long long a = twiceA / 2, b = sums[i] - a, c = sums[j] - a;
            if (b <= 0 || c <= 0) continue;
            for (long long sum : sums) for (long long x : {a, b, c}) {
                long long d = sum - x;
                if (d <= 0) continue;
                array<long long, 4> values{a, b, c, d};
                sort(values.begin(), values.end());
                multiset<long long> all;
                for (int p = 0; p < 4; ++p) for (int q = p + 1; q < 4; ++q)
                    all.insert(values[p] + values[q]);
                bool valid = true;
                for (long long known : sums) {
                    auto it = all.find(known);
                    if (it == all.end()) { valid = false; break; }
                    all.erase(it);  // Repeated sums consume separate copies.
                }
                if (valid) answers.insert(values);
            }
        }
    return answers;
}

例子与复杂度。对 \(\{3,5,6,10,12\}\)，候选 \((1,2,4,8)\) 的六和为 \(\{3,5,6,9,10,12\}\)，缺9。代码同时排查其他候选。由于观测恒为五个，枚举次数与整数数值大小无关；按固定宽度整数运算计为常数时间、结果集合空间为常数级。代码要求两两和及中间加减能放进 long long；更大输入须改任意精度。

建模。只有两顶红帽。第一人的视野是第二、三人的帽子；他能确定自己颜色的唯一情形是看见两顶红（红帽只有两顶，全在别人头上，自己必蓝）。他说「不知道」，这句话对全世界广播了一条信息：第二、三人不同时戴红。第二人接收这条信息后仍只能看第三人：若第三人戴红，则由「不同时红」，第二人立刻推出自己必蓝；他说「不知道」，等于广播：第三人不是红。第三人是盲人，但两条广播加起来足以定案。

推导。把推理链形式化。记三人为 \(P_{1},P_{2},P_{3}\)，帽色 \(c_i \in \{B, R\}\)，红帽总数 2。第一句：\(P_{1}\) 不知道 \(\Rightarrow \neg(c_{2}=R \wedge c_{3}=R)\)。第二句：\(P_{2}\) 已知上式且看见 \(c_{3}\)。若 \(c_{3}=R\)，则「二、三不同时红」迫使 \(c_{2}=B\)，\(P_{2}\) 本可立刻自知为蓝；他仍说不知道，唯一可能是 \(c_{3}=R\) 这个情形本身不成立，故 \(c_{3} \ne R\)。结论：

第三人戴蓝色帽子。

检验。例如第三人蓝、第二人红时，第一人看到红蓝，不知道自己颜色；第二人看到第三人蓝，结合第一句仍不能排除自己红或蓝，因此第二句也成立。若第三人红，则第一句排除第二人红，第二人本应知道自己蓝，与他说“不知道”矛盾。这只用到必要的可见信息，不需要第三人看任何帽子。

面试怎么讲。「盲人听到的是两条信息：第一句排除『二、三两人同时红』，第二句在这个基础上排除『第三人红』——所以第三人必蓝。」可以补一句推广：若有 \(k\) 顶红帽、\(k+1\) 个人依次说不知道，前 \(k\) 句「不知道」逐层把红帽往下挤，第 \(k+1\) 个发言者必能宣布自己蓝色——本题是 \(k=2\) 的最小版本，和「黑帽白帽连续不知道」是同一家族。

建模。先写对称性答案再解剖悖论。设你信封金额为 \(Y\)，另一封为 \(Z\)。拿信封是完全对称的随机动作，\((Y, Z)\) 与 \((Z, Y)\) 同分布，因此 \(\mathbb{E}[Y] = \mathbb{E}[Z]\)，换与不换的期望完全相同。再看著名的错误论证：设看到金额 \(v\)，「另一封以一半概率是 \(2v\)、一半概率是 \(v/2\)」，于是：

照此推理永远该换——但「换完再看一次」又能推出该换回来，荒谬。

推导。错误出在那两个 \(1/2\)：它们不是概率，而是被默认的先验。正确的条件期望要引入后验权重 \(q(v) = \Pr[\text{你拿的是小信封} \mid Y = v]\)：

该换的条件是它大于 \(v\)，化简（\(v \gt 0\)）得 \(3q(v) \gt 1\)，即 仅当你拿小信封的后验概率超过 \(1/3\) 时才值得换。而 \(q(v)\) 由信封金额 \(x\) 的先验分布决定：在某些具体先验下，看到很大的 \(v\) 时 \(q(v)\) 偏小，不该换；看到很小的 \(v\) 时 \(q(v)\) 偏大，该换。要让错误论证成立需要 \(q(v) \equiv 1/2\) 对一切 \(v\) 成立，在常见密度模型下会要求尺度不变的非正规权重；它不能作为任意金额上的合法等概率后验假设——这样的概率分布不存在（测度无法归一）。所以「无条件该换」从来不是合法结论。

检验。总是交换与总是不交换，在打开前因对称而有相同期望；这不意味着“看过金额后再决定”的所有策略等价。若已知两封只有10和20，看见10就换、看见20就不换，最终恒得20，优于无条件策略的均值15。原题未给金额生成先验，因此不能从看到的金额独立算出 q(v)。期望比较还须假设有关期望存在。

面试怎么讲。分三层：「第一，对称性说明换不换期望相同；第二，1.25 倍论证的错在于把两种情形的后验权重想当然设为一半，这需要一个不存在的无界均匀先验；第三，正确的条件换法是：看到金额后估计自己拿小信封的后验概率，超过三分之一才换。」能讲到第三层（并且说出 \(1/3\) 这个阈值）的候选人极少，这是这道经典题的满分线。