建模。套 \(V_{k} = \mathbb{E}[\max(X, V_{k-1})]\)，免费重掷 \(c=0\)：\(V_{0} = \mathbb{E}[X] = 3.5\)，则

推导。阈值规则：重掷当且仅当 \(x \lt 3.5\)，即掷出 1、2、3 重掷，4、5、6 收下。逐项验证阈值两侧：掷出 4 时收下得 4，重掷只得 3.5，收下更优；掷出 3 时重掷 3.5 大于收 3，重掷更优。期望价值 4.25 元：相对不重掷的 3.5 元，重掷权为你增加了 0.75 元。

检验。另一条独立算法：条件分解 \(V_{1} = \tfrac{3}{6} \times 3.5 + \tfrac{3}{6} \times \tfrac{4+5+6}{3} = 1.75 + 2.5 = 4.25\)，一致。边界自查：若重掷无限次，价值趋于 6（永远挑到 6 才停）；若只能重掷零次，价值 3.5——4.25 落在两者之间且偏近下端，合理，因为只有一次机会。

面试怎么讲。「先算不重掷的价值 3.5，它就是继续价值，于是策略是低于 3.5 就重掷；期望 \(\mathbb{E}[\max(X,3.5)] = 4.25\)。」一句话点出「继续价值即阈值」，再报数。变式准备：重掷收费 1 元，阈值变为 \(3.5-1 = 2.5\)，只有掷出 1、2 才值得重掷；更多重掷次数的版本在025 章例题 1 展开。

建模。无限视野的最优停止问题，但策略应为一个固定阈值 \(t\)：收下一切 \(x \ge t\)，重掷一切 \(x \lt t\)。在给定 \(t\) 下求平稳价值 \(V(t)\)，再对 \(t\) 求最优。重掷概率 \(\tfrac{t-1}{100}\)，收下时条件期望 \(\tfrac{t+100}{2}\)，重掷花费 1 美元后回到同款局面：

推导。解出 \(V\) 关于 \(t\) 的表达式：两边乘 100、移项合并 \(V\) 项：

第一项随 \(t\) 线性上升（更挑剔则收下的均值更高），第二项是重掷费的惩罚。逐点比较整数阈值：\(V(86) \approx 93 - 5.67 = 87.33\)，\(V(87) \approx 93.5 - 6.14 = 87.36\)，\(V(88) \approx 94 - 6.69 = 87.31\)。最优阈值 \(t^{*} = 87\)，期望价值约 87.4 美元。策略结构：掷出 87 及以上收下，86 及以下付 1 美元重掷。

检验。数量级直觉：不重掷价值 50.5；免费无限重掷价值 100。付费 1 美元的重掷权居然把价值推到 87，说明「便宜的多次重掷权」极其强大——这正是期权价值的雏形（重掷权 = 看跌期权，见038 章）。阈值偏高（87 而非 51）的原因：费用低到几乎可忽略时，最优行为逼近「只收最高的那些点数」。若重掷免费，同样方程去掉费用项给出 \(V(t) = \tfrac{t+100}{2}\)，阈值推到 100、价值 100——一致。

面试怎么讲。面试官明说「不必算出最终数值」，要的是结构：「最优策略是阈值策略——点数不低于 \(t\) 就收，否则付 1 美元重掷；\(t\) 由『收下均值上升』与『重掷费用与次数的平衡』决定，数值大约在 87 附近，价值约 87.4。」再补一句单调性：「费用越贵阈值越低，费用趋于零阈值趋于 100」——展示你理解阈值怎么随参数移动，比报出精确数字更值钱。

建模。这是「猜对/猜错」的 0-1 损失，最优猜测是 MAP（知识点二）。设你看到的 10 个数中最大值为 \(M\)。似然函数：

怎么读：从 1 到 \(N\) 里抽 10 个数，每个都是 \(\tfrac{1}{N}\) 的概率；同时任何数超过 \(N\) 的情形概率为零，所以似然在 \(N \ge M\) 上是 \(\tfrac{1}{N^{10}}\)，其余为零。先验是 \(\tfrac{1}{1000}\) 常数，因此后验 \(\Pr[N \mid D]\) 在 \(N = M, M+1, \dots, 1000\) 上正比于 \(N^{-10}\)。

推导。\(N^{-10}\) 严格递减，最大值在 \(N = M\) 取得。由于损失是 0-1 型（猜对/猜错），最大化胜率就是取后验众数：

猜你看到的最大值。胜率也不难估：\(\Pr[N=M \mid D] = M^{10} \big/ \sum_{j=M}^{1000} j^{10}\)。由于 \(j^{-10}\) 衰减极快，分母几乎等于 \(M^{10}(1 + (1+\tfrac{1}{M})^{-10} + \cdots)\)，第二项已小于 \((11/10)^{-10} \approx 0.386\)，实际胜率通常在 70% 以上。

检验。直觉核查：\(N\) 不可能小于 \(M\)（观测支撑集），而大 \(N\) 需要十个数恰好全挤在低处的巧合，似然惩罚是十次方的——所以「就猜最大值」既符合直觉又有公式背书。损失函数敏感性：若改罚 \(|\hat{N} - N|\)，最优猜测会略高于 \(M\)（后验均值大于众数），说明「怎么猜」取决于「错了怎么罚」，这一句是面试的加分反思。

面试怎么讲。「0-1 损失下取 MAP：似然 \(\propto N^{-10}\) 在 \(N \ge M\) 上递减，所以猜 \(M\)。」再主动补损失函数的讨论。这题把博弈题还原成了028 章的估计题——认出「这其实是统计」本身就是答案的一半。

建模。第 \(t\) 步兔子在 \(p + m t\)。兔子的整条轨迹由参数对 \((p, m) \in \mathbb{Z} \times \mathbb{Z}\) 决定，可数多个。你每步只能检查一个位置，看似不可能覆盖——除非把「参数对」而不是「位置」当作搜索对象：第 \(t\) 步检查第 \(t\) 对参数所预言的兔子位置。

推导。把 \(\mathbb{Z} \times \mathbb{Z}\) 排成序列 \((p_{1}, m_{1}), (p_{2}, m_{2}), \dots\)，要求每对参数出现在有限下标处——标准做法是对角线枚举（dovetailing）：按 \(|p| + |m| = k\) 分层，第 \(k\) 层有限多对，逐层列出。策略：第 \(t\) 步打开盒子：

若真实参数是 \((p^{*}, m^{*})\)，它在序列中的下标记为 \(t^{*}\)（有限）。那么第 \(t^{*}\) 步你检查的正是 \(p^{*} + m^{*} t^{*}\)——恰好是兔子此刻的位置。必然抓到。注意策略完全不需要知道 \(t^{*}\) 是多少，「有限」就够了。

检验。为什么朴素策略失败：固定猜速度 \(m=1\) 从左往右扫——若兔子 \(m=2\) 同向，永远追不上；对每个速度分别扫到底——每轮无穷长，轮不到第二轮。失败根源都是「在无穷对象上串行穷举」。dovetailing 的修复在于交错推进：所有参数对的检验同时「欠着账」，每个账都有限步内结清。这也解释了为什么要求 \(p\)、\(m\) 是整数（可数）：若 \(m\) 可取任意实数，参数不可数，任何可数步策略都无法覆盖。

面试怎么讲。「能。把 \((p,m)\) 按对角线排成序列，第 \(t\) 步查第 \(t\) 对参数预言的位置 \(p_{t} + m_{t} t\)。真实参数对的检验时机有限，到点即抓到。」再补可数性边界（实数速度则无保证）。这题考的是把「物理上抓兔子」翻译成「参数空间搜索」——模型转译能力本身就是面试考点。

建模。三人对称博弈，胜利条件「最小且唯一」制造了两种张力：往小写（1 最容易最小），但又不能和别人撞车。先做均衡分析，再谈实际玩法。

推导。第一步：纯策略推荐不稳定。若三人都写 1，无人赢；任何一人改写 2 即独赢——「全写 1」不是均衡。一般地，考察纯策略组合：三数全同时，改成 1（若原数大于 1）或改成 2（若原数是 1）就能赢，存在偏离动机；两数相同时（如 \(1,1,c\)），写 \(c\) 的人改写 2 即赢，也有偏离动机。有趣的是三数互不相同的组合确实是纯策略纳什均衡（如 \(1,2,3\)：写 1 者已赢，写 2、3 者无论改写什么都只会让他人赢）——但这种均衡要求三人凭空协调「谁写 1」，对对称的局中人不构成可执行的推荐。第二步：对称解必须混合。设每人独立按同一分布抽取。均衡化条件：分布支撑里的每个数 \(k\) 胜率应相等（否则把概率挪向胜率高的数）。以支撑 \(\{1,2,3\}\) 为例做近似计算：设分布 \((p_{1}, p_{2}, p_{3})\)，写 1 的胜率是「别人都不写 1」的概率 \((p_{2}+p_{3})^{2}\)；写 2 的胜率是「别人要么都写 1、要么都不写 1 也不写 2」的概率 \(p_{1}^{2} + p_{3}^{2}\)；写 3 的胜率是 \(p_{1}^{2}+p_{2}^{2}\)。令三者相等解得 \(p_{1} \approx 0.46,\ p_{2} = p_{3} \approx 0.27\)。第三步：诚实声明边界。在这个三数分布下，改写 4（三人撞车时 4 也可能成为最小唯一）的胜率并不更差，说明真正的对称均衡要把质量摊到更多数上、按近似几何速度衰减——精确分布超出面试范围，思路到此已够。

检验。胜率口径核对：\(p_{1}=0.46, p_{2}=p_{3}=0.27\) 下单人胜率约 \((0.54)^{2} \approx 0.29\)，三人合计约 0.86，其余约 0.14 的概率出现撞车无人赢——量级合理。策略直觉核对：分布质量大头在 1、2，与「最小者赢」的激励方向一致；尾部衰减体现「写大数要靠别人撞车」的弱激励。

面试怎么讲。分三段：「纯推荐不稳定——全写 1 无人赢，有人改 2 就赢，循环往复；互不相同的三数虽是均衡但需要无法实现的协调；所以对称解是混合策略，把主要概率放在 1、2、3 上并快速衰减。」面试官要听的是均衡论证的过程（偏离—修复—再偏离的循环），不是精确分布。

建模。三场独立，胜率依次为 \(p_{1}, p_{2}, p_{3}\)。「连续赢两场」等价于赢下第 2 场且至少赢下第 1、3 场之一：

怎么读：中间那场在两条连赢路径（1-2 与 2-3）上都必经，所以它单独作乘性因子；两端至少赢一场用容斥。这个分解立刻给出直觉——把最有把握的一场放在中间，两端「两张彩票」用容斥合并。

推导。记 \(p_{F} = 0.5\)、\(p_{B} = 0.05\)。BFB（中间是父亲）：\(P_{\text{BFB}} = 0.5 \times (0.05 + 0.05 - 0.0025) = 0.5 \times 0.0975 = 0.04875\)。FBF（中间是兄弟）：\(P_{\text{FBF}} = 0.05 \times (0.5 + 0.5 - 0.25) = 0.05 \times 0.75 = 0.0375\)。等价地按事件分解核对 \(P_{\text{BFB}}\)：赢第 1、2 场 \(0.05 \times 0.5\)，加上输第 1 场后赢 2、3 场 \(0.95 \times 0.5 \times 0.05\)，合计 \(0.025 + 0.02375 = 0.04875\)。选 BFB，胜率约 4.9% 对 3.8%。

检验。直觉核查：中间场是瓶颈，胜率 0.5 的对手理应占据瓶颈位；强敌（兄弟）放在两端，只需在两张 5% 彩票中命中一张，而不是在必经之路上全取。反事实检验：若目标改为「三场至少赢两场」（多数胜），结构完全不同——FBF 下赢两场父赛的 \(0.25\) 占主导，\(P_{\text{FBF}} = 0.275\) 远大于 \(P_{\text{BFB}} = 0.05\)，结论反转。这说明「连胜」与「多数胜」是两个不同的优化问题，面试官最爱在这个分叉口追问。

面试怎么讲。「连续两胜必经中间场，所以把五成胜率的父亲放中间：BFB，胜率约 4.9%，高于 FBF 的 3.8%。」然后主动抛出反转：「如果目标是赢下多数场，答案反过来选 FBF——两场对父亲的比赛是主要得分来源。」公式一个、数字两行、变式一个，这道题就答满了。

建模。设坏糖果在第 \(r\) 行第 \(c\) 列。任何时刻局面由「尚存的行集合与列集合」决定。吃掉第 \(r\) 行或第 \(c\) 列的人立刻吃到坏糖果、输掉——所以理性人绝不主动碰这两条线，直到无别的选择。于是所有安全着法就是：吃掉 \(r\) 之外的行（共 \(N-1\) 条）或 \(c\) 之外的列（共 \(N-1\) 条）。

推导。关键计数：安全着法的总数是：

与行、列被吃的顺序无关，永远是偶数。两个理性人轮流消耗安全着法，\(2N-2\) 步之后局面必然收缩为「只剩第 \(r\) 行和第 \(c\) 列」，即矩阵只剩坏糖果一颗；这时轮到的先手无路可走，只能吃坏糖果。当后手。后手还有一个漂亮的具体走法（配对策略）：把 \(N-1\) 条安全行与 \(N-1\) 条安全列任意两两配对，对方每吃一条线，你就吃它的配对线——对方的每个安全着法都有安全回应，坏糖果必然最终留给对方。顺带一提，先手也救不了自己：不吃坏线就只剩安全线可耗，而安全线总数是偶数，先手注定最后一个「无安全着法」的人（\(N=1\) 的退化情形同样成立：先手第一步就面对坏糖果）。

检验。小例核对 \(N=2\)：四颗糖、一颗坏。先手吃安全行（或列），后手吃安全列（或行），只剩坏糖果给先手——先手输，与公式 \(2N-2 = 2\)（偶数）一致。对比类题目：Chomp 类「吃毒巧克力」博弈先手有偷策略论证（strategy stealing）可赢，本题不行——因为先手任意第一步都只是消耗一条安全线，没有「额外一手」可占，奇偶性主导结局。这是「结构论证（计数与配对）先于策略搜索」的范例。

面试怎么讲。「当后手。坏糖果的行列没人敢碰，安全着法恰好 \(2N-2\) 条、恒为偶数，耗尽后被迫吃坏糖果的一定是先手；后手还可以用行列配对法保证回应。」计数、配对、小例验证三件套讲完，这类位置博弈基本就结束了。