WorldQuant 数学笔试：30 道原题逐步解析

原题 1 · Fungi Population：随机涨跌后的平均规模

原题位置：PDF 第 5 页。题型：期望、乘法变化、条件平均。

完整题意

一种真菌的种群规模每分钟变化一次：增加当前规模的 5%，或者减少当前规模的 5%，两种情况发生的可能性相同。问 60 分钟后，种群规模的期望与初始规模相比如何？选项：与初始规模相等；信息不足；小于初始规模；大于初始规模。

先补基础

期望是把各个可能结果按其发生概率加权平均。例如，规模为 100 时，下一分钟可能变成 105 或 95，两者各占一半，平均就是 100。增加 5% 对应乘以 1.05，减少 5% 对应乘以 0.95。

解题方法：先固定当前规模，只算下一步的平均，再重复应用。按通常的随机涨跌模型，每一分钟在已知过去变化后，涨、跌的概率仍各为一半。

1. 记下当前规模。用 \(N_t\) 表示第 \(t\) 分钟的规模，\(N_0\) 是初始规模。
2. 算下一分钟的条件平均。当前若有 \(N_t\) 个，下一分钟的平均规模为
   \[\frac12(1.05N_t)+\frac12(0.95N_t)=N_t.\]
   无论当前具体规模是多少，这个等式都成立。
3. 把所有当前状态再平均。既然每个状态下一步的平均都等于该状态自身，整体平均也保持不变。因此 \(\mathbb E[N_{t+1}]=\mathbb E[N_t]\)。
4. 连续应用 60 次。得到 \(\mathbb E[N_{60}]=N_0\)。

易错点：先涨一次、再跌一次确实得到 \(1.05\times0.95=0.9975\)，但这只是一类路径，不能代替全部路径的平均。期望相等也不保证每次实验最终都回到原规模。

题意边界：若只知道“每个时刻单独看涨跌各占一半”，却允许所有时刻完全相关，结论不一定成立。例如先抛一次硬币，随后 60 次全部涨或全部跌，期望会变成 \(N_0(1.05^{60}+0.95^{60})/2\)。因此题目的标准答案依赖通常采用的逐步随机机制；独立涨跌足以保证这一点。

原题 2 · Uniform probability：把概率转成面积

原题位置：PDF 第 6 页。题型：独立均匀分布、几何概率。

完整题意

随机数 \(X\) 在 \([0,1]\) 上均匀分布，\(Y\) 在 \([0,3]\) 上均匀分布，且二者相互独立。求 \(P(X+Y\lt2/3)\)。选项为 \(2/9,4/27,2/27,1/9\)。

先补基础

在一个区间上均匀分布，表示等长的小区间有相同概率。独立则表示知道 \(X\) 的值不会改变 \(Y\) 的分布。两者合起来，点 \((X,Y)\) 就均匀落在宽 1、高 3 的长方形里；某个区域的概率等于该区域面积除以长方形总面积。

解题方法：画出全部可能结果，再画出满足不等式的区域。

1. 确定总区域。横坐标在 0 到 1 之间，纵坐标在 0 到 3 之间，总面积为 \(1\times3=3\)。
2. 画出边界直线。\(x+y=2/3\) 与横、纵轴的交点分别是 \((2/3,0)\) 和 \((0,2/3)\)。
3. 找出有利区域。\(x+y\lt2/3\) 对应靠近原点的直角三角形，它的两条直角边都长 \(2/3\)，面积为
   \[\frac12\times\frac23\times\frac23=\frac29.\]
4. 用有利面积除以总面积。
   \[P(X+Y\lt2/3)=\frac{2/9}{3}=\frac{2}{27}.\]

易错点：\(2/9\) 是面积，还没有除以总面积 3。这里随机点的分布范围不是单位正方形。直线边界的面积为 0，所以把严格小于换成小于等于，不会改变本题概率。

原题 3 · Folded paper：折纸外露颜色的组合数

原题位置：PDF 第 7 页。题型：不变量、组合计数、构造与可实现性。

完整题意

一张纸由四条平行折痕分成五个全等长方形。五个长方形的正反两面分别涂上不同颜色，共十种颜色。沿原来的折痕将纸完全折叠，允许改变折叠顺序和向上、向下的方向。折好后外侧露出两种颜色，问能够得到多少种不同的双色组合？同一双色组合把整叠纸翻过来，仍算一种。

先补基础

先给五片纸从左到右编号 1 至 5。记第 \(i\) 片原来朝上的颜色为 \(A_i\)，朝下的为 \(B_i\)。纸折过 180 度，正反朝向会交换。相邻两片完全重合后，它们的正面朝向必然相反；因此，奇数编号片的朝向彼此相同，偶数编号片的朝向彼此相同，奇、偶两组方向相反。

解题方法：先利用朝向不变量给出最多多少种，再提供折法说明每一种都能做到。只做第一步还不能证明答案。

1. 统一观察方向。整叠纸翻面不会改变双色组合，因此可以统一令第 1 片的 \(A_1\) 面朝上。这时五片朝上的颜色固定为
   \[A_1,\ B_2,\ A_3,\ B_4,\ A_5,\]
   五片朝下的颜色固定为 \(B_1,A_2,B_3,A_4,B_5\)。这两组各有五种不同颜色，且没有重合。
2. 数出上界。最上层是哪一片有 5 种选择；最下层必须是另一片，有 4 种选择。所以上、下外露颜色最多有 \(5\times4=20\) 种。它们不会因“双色组合无顺序”而再除以 2，因为一种颜色属于固定的朝上组，另一种属于固定的朝下组。
3. 证明这些候选都可以折出。下面给出十组端点各自的一种实际折法。初始时五片平铺且 \(A_i\) 朝上。每一步都按当前占据的列从左到右重新编号；“左2上”表示将当前最左两列连同全部层向右翻折，放到固定部分上面；“左2下”表示放到下面；“右1上”表示将分界线右边的部分向左翻到上面。右折中的数字同样表示分界线左边有几列。最终层序按从下到上书写。

4. 得到另外十种。把一行折法里的“上”全部换成“下”，“下”全部换成“上”，相当于把整个折叠过程上下镜像。最终每片的正反朝向不变，层序却倒置，所以最上、最下两片交换，露出的是它们各自的另一面。十种端点组合各给两种不同颜色对，共 20 种。
5. 上下界一致。最多 20 种，且已经构造出 20 种，因此答案确定。

易错点：不能从十种颜色中任取两种，写成 \(\binom{10}{2}=45\)：朝向和同一片不能同时占据最上、最下层都会限制组合。也不能把所有内部层序当作不同答案；许多层序露出的颜色完全相同。题目采用的是纸片厚度忽略不计、沿原折痕完全重合的通常折纸模型。

原题 4 · Pure Arithmetic：巨大整数有多少位

原题位置：PDF 第 8 页。题型：对数、数量级、指数运算顺序。

完整题意

求表达式 2023^4^5 所表示整数的十进制位数，并从 3000、3100、3200、3300、3400、3500 中选择最接近的数。

先补基础

一位正整数在 \(1\) 到 \(9\) 之间，两位正整数在 \(10\) 到 \(99\) 之间。一般地，正整数 \(N\) 恰有 \(d\) 位，当且仅当 \(10^{d-1}\le N\lt10^d\)。以 10 为底的对数 \(\log_{10}N\) 表示“10 的多少次幂等于 \(N\)”。

解题方法：把“大数有几位”改写成“对数的整数部分是多少”。

1. 先确认指数顺序。连续乘方按通常的数学约定从右往左结合，即
   \[2023^{4^5}=2023^{1024}.\]
   给出的选项也与这个解释相符。
2. 推出位数公式。对 \(10^{d-1}\le N\lt10^d\) 取对数，有 \(d-1\le\log_{10}N\lt d\)，所以
   \[d=\lfloor\log_{10}N\rfloor+1.\]
   \(\lfloor x\rfloor\) 表示不超过 \(x\) 的最大整数。
3. 把幂移到对数前面。
   \[\log_{10}(2023^{1024})=1024\log_{10}(2023)\approx3385.339784.\]
   因此实际位数为 \(3385+1=3386\)。
4. 对应题目要求选择近似值。3386 距 3400 为 14，距 3300 为 86，因此最接近的选项为 3400。

不用精细计算也能选对：\(\log_{10}2023\) 约为 \(3.3\)，乘以 1024 约为 3380，已经足以判断最接近 3400。

易错点与记号边界：\((2023^4)^5=2023^{20}\) 与 \(2023^{4^5}\) 完全不同，前者只有 67 位。原文使用连续的 ^，书写不够严谨；这里按数学乘方的右结合约定与选项范围解释。

原题 5 · Old book：页码总和与一张纸的两面

原题位置：PDF 第 9 页。题型：等差数列求和、整数约束、题意辨析。

完整题意

一本旧书的页码从 1 开始连续编号。一页被完整撕掉后，剩余页码的总和为 757。问这本书有多少页？选项：38、40、41、42。

先补基础与口径

书的一张纸有正反两个编号页。按通常的双面分页，某张纸上的页码是 \(2k-1\) 和 \(2k\)，总和为 \(4k-1\)。同时，\(1+2+\cdots+N=N(N+1)/2\)：可以把首尾配对，每对之和都是 \(N+1\)。

解题方法：用“原有页码总和 − 被撕页码总和 = 剩余总和”建立方程。还须区分“原有多少个编号页”和“撕掉后还剩多少个编号页”，这两问相差 2。

1. 设原有编号页为 1 至 \(N\)。设撕去的一张纸对应 \(2k-1,2k\)，则
   \[\frac{N(N+1)}2-(4k-1)=757.\]
2. 若选项询问原有页数，逐项检查。原有 38 页时全部页码相加才 741，小于 757，不可能。原有 41 页时总和为 861，即使去掉两个最大的页码，剩余也至少 \(861-40-41=780\)，仍太大。原有 42 页时最少还剩 \(903-41-42=820\)，也太大。
3. 检查原有 40 页。总和为 \(40\times41/2=820\)，撕去的页码之和应为 \(820-757=63\)。两个连续页码为 \((63-1)/2=31\) 和 \(32\)，确实是同一张纸的两面。
4. 分别回答两种页数。原书的编号范围为 1 至 40；撕掉两个编号页后，实际保留下来的是 \(40-2=38\) 个编号页。

原文歧义：英文用 one page 表示被撕的一页，并问 How many pages are there in the book?，没有明确原有还是现存，而 38 和 40 都出现在选项中。PDF 没有提供答案标记，因此不能据此确认官方采用哪一种口径。

额外条件为何重要：如果将 page 理解成只少一个编号面，原有 39 个编号页并少掉第 23 页，也会得到 757。甚至允许原书编号在奇数 39 结束时，撕去第 11、12 页也满足条件。通常的“完整双面分页、原页数为偶数”解释及题目给出的原页数候选，才会确定原有 40 页。考试中应先确认“纸张、编号页、原有、剩余”各指什么。

原题 6 · Knights：最多能放多少个互不攻击的马

原题位置：PDF 第 10 页。题型：棋盘染色、最大值构造、配对上界。

完整题意

在 \(5\times5\) 的国际象棋棋盘上，最多可以放多少个马，使任意两个马都不能相互吃掉？马每次走两格横向加一格纵向，或者两格纵向加一格横向；这里采用国际象棋规则，不考虑中国象棋的“蹩马腿”。

先补基础

求最大值通常要做两件事：给出一种能达到该数量的摆法，再证明更多数量不可能。只给一个摆法，证明的只是“至少能放这么多”。

解题方法：用黑白染色构造 13 个马，再将棋盘中的 24 格配成 12 对相互攻击的位置，证明上界也是 13。

1. 给棋盘黑白相间染色。把左上角染黑，则五行黑格数依次为 \(3,2,3,2,3\)，共 13 个；白格共 12 个。
2. 说明同色马互不攻击。把格子记为行、列坐标 \((r,c)\)。马一次移动会让 \(r+c\) 的奇偶性改变，因为 \(2+1\) 是奇数。因此每次一定从黑格跳到白格，或从白格跳到黑格。把 13 个马放满全部黑格即可。
3. 证明不能放 14 个。下表中同一字母出现两次，这两格相差“一行两列”或“两行一列”，可以相互攻击。中间的点表示一个未配对格。

A F B D C
H D A E B
F J · C G
K H L I E
J I K G L

4. 逐对限制数量。例如 A 在 \((1,1)\) 与 \((2,3)\)，这两个位置至多放一个马；其余 B 至 L 同理。12 对至多放 12 个，中间的单独一格至多再放 1 个，总计不超过 13。
5. 合并结论。既有能放 13 个的摆法，又证明无法超过 13，所以最大值恰为 13。

易错点：“一共有 13 个黑格，所以最多 13 个”缺少上界证明，因为原则上也可能存在混合使用黑格和白格的更好摆法。配对论证正是为了排除这种可能。

原题 7 · Ratio of product sum and difference：从比例建立方程

原题位置：PDF 第 11 页。题型：比例设参、二元方程。

完整题意

两个数的积、和、差之比为 \(24:7:1\)，求这两个数的和。原图最后一项是 1，后面跟问号；不是 12。

先补基础

“三个量之比为 \(24:7:1\)”表示它们分别是同一个非零量的 24 倍、7 倍和 1 倍。比例只规定相对大小，不能直接把三者当成 24、7、1。

解题方法：引入一个共同的比例系数，再把和、差相加减以求出两个数。

1. 设置未知数。把较大的数记作 \(x\)，较小的记作 \(y\)。设共同的比例系数为 \(t\)，则
   \[xy=24t,\qquad x+y=7t,\qquad x-y=t.\]
2. 由和与差恢复原数。后两个等式相加得 \(2x=8t\)，所以 \(x=4t\)；相减得 \(2y=6t\)，所以 \(y=3t\)。
3. 使用积的条件。代入 \(xy=24t\)：
   \[12t^2=24t.\]
   比例系数不能是 0，所以除以 \(12t\)，得到 \(t=2\)。
4. 计算并回代检查。\(x=8,y=6\)，和为 14；积为 48，差为 2，确有 \(48:14:2=24:7:1\)。

易错点：答案不是比例里的 7；还需要求出比例系数。解方程时会出现形式上的 \(t=0\)，但三个量全为 0 时给定的比例没有意义，必须舍去。

原题 8 · Number Genetics：数字重排、整除与抽屉原理

原题位置：PDF 第 12 页。题型：数位和、模运算、抽屉原理、最大值构造。

完整题意

对一个十进制整数 \(M\)，记 \(D(M)\) 为使用 \(M\) 的部分或全部数字、按任意顺序排列可以组成的整数集合；每个数字最多使用它在 \(M\) 中出现的次数。例如，\(M=2024\) 可以组成 0、2、4、20、22、24、202、220、2024 等整数。求最大的 \(M\)，使 \(D(M)\) 中没有任何整数能被 9 整除。

先补基础

被 9 整除的判定：一个整数除以 9 的余数，等于它的各位数字之和除以 9 的余数。例如 \(234\) 的数位和为 \(2+3+4=9\)，所以它能被 9 整除。理由是 \(10,100,1000,\ldots\) 除以 9 都余 1。

抽屉原理：把十个对象分到九类，至少有两个对象属于同一类。本题的九类就是余数 \(0,1,\ldots,8\)。

解题方法：先证明合法数字不能达到九位，再构造最大的合法八位数。

1. 排除数位 0 和 9。只要 \(M\) 含 9，就可以单独取出 9；含 0，则可单独取出 0。0 也能被 9 整除，因为 \(0=9\times0\)。所以每一位只能是 1 至 8。
2. 假设它至少有九位。任取其中按原顺序排列的九位，记为 \(a_1,\ldots,a_9\)。考虑下面十个“前面若干位的数字和”：
   \[S_0=0,\quad S_1=a_1,\quad S_2=a_1+a_2,\quad\ldots,\quad S_9=a_1+\cdots+a_9.\]
3. 找出两个相同余数。十个数除以 9 只有九种余数，因此必有 \(S_i,S_j\) 的余数相同，其中 \(i\lt j\)。两者相减，得到
   \[S_j-S_i=a_{i+1}+\cdots+a_j\equiv0\pmod9.\]
   这里 \(\equiv0\pmod9\) 表示“除以 9 的余数为 0”。因此，取出这一段数字组成的非空整数就能被 9 整除，违反要求。
4. 得出位数上界。任何合法 \(M\) 至多有八位。又因为每一位至多为 8，所以它不会超过 \(88888888\)。
5. 检查这个上界确实合法。从八个 8 中取 \(k\) 个，其中 \(1\le k\le8\)，所得数的数位和为 \(8k\)。因为 8 与 9 没有大于 1 的公因数，\(8k\) 能被 9 整除要求 \(k\) 本身能被 9 整除，而 1 至 8 都做不到。

易错点：只检查 \(M\) 本身不能被 9 整除不够，任取部分数位组成的数也要检查。另一方面，无须真的枚举全部重排，因为整除性只取决于选中数位的和。

原文例子的边界：原图的 \(D(2024)\) 列表没有列全，例如 402、420、422 也符合其文字定义。上面的解答按“从原数位中任取非空部分并重排”的定义处理，不把不完整的示例列表当作额外限制。

原题 9 · Bishop Moves：按移动距离统计有向走法

原题位置：PDF 第 13 页。题型：分类计数、平方和、有序与无序的区别。

完整题意

一个国际象棋的象在 \(12\times12\) 棋盘上沿对角线移动任意正整数格。把棋盘上所有可能起点、终点的合法一步移动合起来，共有多少种？题目举例：\(3\times3\) 棋盘有 20 种，A 到 E 与 E 到 A 分别计数。因此本题统计有方向的移动，不是固定某一个象所在格子的可选步数。

先补基础

沿对角线走 \(d\) 格，意味着行号和列号分别改变 \(d\)，方向有右下、左下、右上、左上四种。按距离分类后，不同类别不会重复；同一距离下，确定起点与方向就确定了终点。

解题方法：固定移动距离，数出四个方向的合法起点，再对距离求和。

1. 先固定向右下走 \(d\) 格。为保证终点不出棋盘，起点只能在前 \(12-d\) 行、前 \(12-d\) 列。因此有 \((12-d)^2\) 种。
2. 加入另外三个方向。四个方向对称，每个方向都有同样数量，所以距离为 \(d\) 的移动共 \(4(12-d)^2\) 种。
3. 列出可能距离。距离最小为 1，最大为 11；距离 0 不算移动。因此总数为
   \[4\sum_{d=1}^{11}(12-d)^2=4(1^2+2^2+\cdots+11^2).\]
4. 计算平方和。利用 \(1^2+\cdots+m^2=m(m+1)(2m+1)/6\)，得到
   \[4\times\frac{11\times12\times23}{6}=4\times506=2024.\]
5. 用原题的小棋盘检查口径。在 \(3\times3\) 棋盘上，同样得到 \(4(1^2+2^2)=20\)，与原题一致。

易错点：若把 A 到 E 和 E 到 A 当作同一种，会少算一半。若只算棋盘中心一格出发的走法，也没有回答原题。注意“移动任意距离”仍指一步沿同一条对角线移动，不能转弯。

原题 10 · Cut Square Chocolate：把正方形分成小正方形

原题位置：PDF 第 14 页。题型：按最大块分类、不重叠放置、去重计数。

完整题意

把一块 \(4\times4\) 巧克力分割成若干边长为正整数的正方形，每个 \(1\times1\) 小格必须保持完整。旋转、翻转后得到不同位置安排，分别算不同方案；同一最终分块如果切割顺序不同，只算同一种。完全不切也算一种。原题说明 \(3\times3\) 有六种：不切一整块；一个 \(2\times2\) 加五个 \(1\times1\)，其中大块有四个位置；以及全切成 \(1\times1\)。求 \(4\times4\) 的方案数。

先补基础

每个单位格完整，分块边界就沿格线。可能的正方形边长只有 1、2、3、4。分类计数要求各类别互不重叠且包含所有情况；本题适合先按“有没有 4 块、3 块”分类，剩下的再按 \(2\times2\) 块数量分类。

解题方法：确定所有大于 \(1\times1\) 的块以后，剩余格子都只能各自成为 \(1\times1\)，因此只需要统计较大正方形怎样互不重叠地放置。

1. 含 \(4\times4\) 块。只能完全不切，有 1 种。
2. 含 \(3\times3\) 块。它的左上角有 \(2\times2=4\) 个位置。放下后，剩余区域宽度不足以再放一个 \(2\times2\)，所以剩余七格必须全是 \(1\times1\)。这一类共 4 种。
3. 只含 \(2\times2\) 与 \(1\times1\) 块。一个 \(2\times2\) 块的左上角只能位于下列九个位置，用小写字母标记：

   a b c
   d e f
   g h i

   这张 \(3\times3\) 表表示的是“大块左上角的位置”，不是巧克力本身。两个位置若行号之差至少为 2，或者列号之差至少为 2，放下的两个块才不重叠。
4. 放零块或一块 \(2\times2\)。零块对应全是单位格，有 1 种；一块可从九个位置任取，有 9 种。
5. 放两块 \(2\times2\)。第一种分离方式是一个左上角在第一行、另一个在第三行，有 \(3\times3=9\) 对；第二种是分别在第一列、第三列，也有 9 对。两种方式同时满足时，就是两对对角位置 \(\{a,i\}\)、\(\{c,g\}\)，被各算了两次，所以总数为 \(9+9-2=16\)。
6. 放三块 \(2\times2\)。中心位置 e 与其余八个位置全部冲突，不能用。若三个位置全是角点 a、c、g、i，从四个角点取三个，有 4 种。若用一个边中点，就必须配它对面那条边的两个角点：\(\{b,g,i\},\{h,a,c\},\{d,c,i\},\{f,a,g\}\)，另外 4 种。两个边中点即使互不冲突，也无法再放第三块。因此这一类共 8 种。
7. 放四块 \(2\times2\)。四块面积已是 16，只能四个角点 a、c、g、i 全选，形成通常的四等分，共 1 种。放五块的总面积超过 16，不可能。
8. 相加。
   \[1+4+(1+9+16+8+1)=40.\]

易错点：题目把不同位置的旋转、镜像安排分别计数，不能只数几种形状；但自身旋转后完全不变的同一个分块方案，也不能额外乘 4。还要避免把“先横切再竖切”和“先竖切再横切”重复计数。这里统计最终分割，不附加“每一刀都必须贯穿当前整块”的限制。

原题 11 · Balancer：删除一个数后，怎样使平均数相同？

PDF 第 15 页 · 方法：先算总量，再建立平均数方程 · 难度：基础

完整题意：集合 \(A=\{1,3,5,\ldots,2023\}\)，集合 \(B=\{2,4,6,\ldots,2024\}\)。可以选择从 \(A\) 中拿走一个数 \(a\)，也可以改为从 \(B\) 中拿走一个数 \(b\)，使操作后的两个集合具有相同的平均数。分别求这两种操作所需要的 \(a,b\)。原题选项包括 \((1,2024)\)、\((1013,1012)\)、\((2023,2024)\)、\((2023,2)\)、\((1,2)\)、无解、多于一组解。

先补概念

平均数等于“所有数的和除以个数”。等差数列的平均数等于首尾两项的平均数。删除一个数时，分子要减去这个数，分母也要减去 1。

分步解答

1. 求原来的平均数和个数。两组各有 \(1012\) 个数。\(A\) 的平均数是 \((1+2023)/2=1012\)，总和为 \(1012^2\)；\(B\) 的平均数是 \((2+2024)/2=1013\)，总和为 \(1012\times1013\)。
2. 只从 A 删除。此时 \(B\) 保持不变，所以 \(A\) 的新平均数必须达到 \(1013\)：
   \[\frac{1012^2-a}{1011}=1013\quad\Longrightarrow\quad a=1012^2-1011\times1013=1.\]
   删除最小的数，确实会提高平均数。
3. 只从 B 删除。此时 \(A\) 保持不变，所以 \(B\) 的新平均数必须降到 \(1012\)：
   \[\frac{1012\times1013-b}{1011}=1012\quad\Longrightarrow\quad b=2024.\]
   删除最大的数，确实会降低平均数。
4. 检查是否属于原集合。\(1\in A\)，\(2024\in B\)，因此两种操作都可行。

易错点与题意边界：原文的 “either … or alternatively …” 表示两种备选操作，不是同时从两组各删一个数。若同时删除，则方程变成 \(b-a=1012\)，但偶数减奇数一定是奇数，不可能等于偶数 \(1012\)，这时确实无解。

原题 12 · Square Date：下一个能写成平方数的日期

PDF 第 16 页 · 方法：缩小枚举范围，检查数字所代表的真实条件 · 难度：基础至中等

完整题意：把日期写成八位整数 \(\mathrm{YYYYMMDD}\)。已知 \(20241001=4499^2\)，即 2024 年 10 月 1 日是一个完全平方数日期。2024 年之后，下一个至少有一个完全平方数日期的年份是哪一年？

先补概念

完全平方数是某个整数的平方。整数的平方随正整数本身严格增加。因此按平方根从小到大检查，不会漏掉更早的平方数日期。日期还必须满足月份为 1 至 12，日期确实存在；八位整数有合适的前四位，并不足以保证它是日期。

分步解答

1. 从紧接着的平方根开始。\(4499^2\) 已在 2024 年，所以下一个候选平方根是 \(4500\)。不过 \(4500^2=20250000\)，月份和日期都是 00，不合法。
2. 利用末四位筛选。令平方根为 \(4500+k\)，则
   \[(4500+k)^2=20250000+9000k+k^2.\]
   其末四位必须代表 \(\mathrm{MMDD}\)，数值至少为 \(0101\)，至多为 \(1231\)。对 \(k=0,1,\ldots,52\) 依次计算，末四位不超过 \(1231\) 的候选如下；其余候选的月份都大于 12。

3. 确认“最早”。从 \(4500\) 到 \(4551\) 的平方数都已被月份或日期规则排除；\(4552^2\) 是第一个合法候选。平方根再增大，平方数不会变小，因此不可能产生更早的年份。

易错点：不能只检查年份是否增加，也不能把 01 月 00 日、10 月 81 日当作日期。若使用程序枚举，应检查每个月的实际天数以及闰年规则，而不是只要求日数不超过 31。

原题 13 · Triangle Area：三个交替小三角形等面积

PDF 第 17 页 · 方法：同高三角形的面积比、建立方程、证明唯一解 · 难度：中等

完整题意：\(O\) 是三角形 \(ABC\) 内部一点。直线 \(AO\) 与 \(BC\) 相交于 \(A'\)，直线 \(BO\) 与 \(CA\) 相交于 \(B'\)，直线 \(CO\) 与 \(AB\) 相交于 \(C'\)。用 \(S\) 表示面积，已知 \(S(AOB')=S(BOC')=S(COA')=1\)。问 \(S(ABC)\) 的可能取值范围的长度：若范围是 \([a,b]\)，填写 \(b-a\)。

先补概念

三角形面积为“底乘高再除以 2”。两个三角形若有相同的高，它们的面积之比就等于底边长度之比。本题不需要假设 \(ABC\) 等边，也不能仅凭图形对称就断言 \(O\) 是重心。

分步解答

1. 用三个较大的三角形面积表示未知量。令
   \[x=S(BOC),\qquad y=S(COA),\qquad z=S(AOB).\]
   由于 \(O\) 在内部，三者均为正数，而且 \(S(ABC)=x+y+z\)。
2. 把第一个小面积写成分式。以 \(BO\) 为共同底边，\(S(AOB):S(COB)=z:x\)。又因为 \(A,B',C\) 共线，这一比例也等于 \(AB':B'C\)，所以 \(AB'/AC=z/(x+z)\)。\(AOB'\) 与 \(AOC\) 对 \(AC\) 有相同的高，因此
   \[S(AOB')=y\frac{z}{x+z}=1.\]
   同理，另两条条件分别给出 \(zx/(x+y)=1\) 与 \(xy/(y+z)=1\)。
3. 整理成三个方程。
   \[yz=x+z,\qquad zx=x+y,\qquad xy=y+z.\]
   等价地，
   \[x=z(y-1),\qquad y=x(z-1),\qquad z=y(x-1).\]
4. 证明三个未知量只能都等于 2。方程在循环更换 \(x,y,z\) 后不变，因此可以把最大的一个命名为 \(x\)。由 \(x=z(y-1)\) 及 \(x\ge z\)，得到 \(y\ge2\)。由 \(y=x(z-1)\) 及 \(y\le x\)，得到 \(z\le2\)。但 \(x\ge y\ge2\)，代入 \(z=y(x-1)\)，又得到 \(z\ge y\ge2\)。于是 \(z=2\)、\(y=2\)，再代回得到 \(x=2\)。这排除了全部不对称的正数解。
5. 求范围的长度。大三角形面积只能为 \(x+y+z=6\)。这个值可以实现：取任意面积为 6 的三角形，令 \(O\) 为重心，三条中线将其分成六个面积为 1 的小三角形。因此可能范围就是单点区间 \([6,6]\)。

易错点：原题问的是范围的长度，不是大三角形面积本身，所以不能填 6。题干使用“范围”一词，并不意味着一定存在两个不同的端点；\([6,6]\) 同样是合法的退化区间。

原题 14 · Triangle revisited：随机点到三边距离之和的期望

PDF 第 18 页 · 方法：几何期望、重心、期望的线性性质 · 难度：中等

完整题意：等腰三角形 \(ABC\) 的底边 \(BC=6\)，两个底角 \(\angle ABC=\angle ACB=30^\circ\)。在三角形内部随机选取一点 \(X\)（按此类题的通常约定，采用面积均匀分布），求它到三条边的垂直距离之和的期望。原题选项为 \(1+2\sqrt3\)、\(2+\sqrt3/3\)、\(3+\sqrt3/3\)、\(3\sqrt3\)、\(3\)。

先补概念

“均匀随机选点”表示相同面积的区域有相同的选中概率。一个三角形的均匀质量分布的重心，是三个顶点坐标的平均值。重心到每一条边所在直线的距离，都是相应高的三分之一。

分步解答

1. 求底边上的高。从 \(A\) 向底边作垂线，等腰三角形的底边被平分为两段长度为 3 的线段。因此
   \[h_{BC}=3\tan30^\circ=\sqrt3,\qquad S(ABC)=\frac12\times6\times\sqrt3=3\sqrt3.\]
2. 求腰长和另外两条高。在同一个直角三角形中，\(AB=AC=3/\cos30^\circ=2\sqrt3\)。所以
   \[h_{AB}=h_{AC}=\frac{2S(ABC)}{2\sqrt3}=3.\]
3. 说明为什么可以在重心处计算。对于固定的一条边，三角形内所有点都在它的同一侧。到该边所在直线的距离可写成坐标的线性表达式加常数。因此“距离的平均值”等于“平均坐标处的距离”，也就是重心到该边的距离。
4. 分别取期望再相加。期望满足 \(\mathbb E[U+V+W]=\mathbb E[U]+\mathbb E[V]+\mathbb E[W]\)，不需要三个距离独立。因此
   \[\mathbb E[d_{BC}+d_{AB}+d_{AC}]=\frac{\sqrt3}{3}+\frac33+\frac33=2+\frac{\sqrt3}{3}.\]

题意边界：这里按几何题通常约定，距离指到边所在直线的垂直距离。三角形的顶角为 \(120^\circ\)；若把“到边的距离”严格解释成到有限线段的最短距离，部分垂足会落在线段延长线上，问题与答案都会改变。上面的约定与给定选项一致。

易错点：只有等边三角形中，各点到三边距离之和才处处相同。本题是等腰钝角三角形，距离之和随点变化；能在重心处求出的是期望。

原题 15 · Distances in a Circle：较近距离的分位数

PDF 第 19 页 · 方法：把概率事件变成圆环面积、补事件、单位换算 · 难度：基础至中等

完整题意：在半径为 2 米的圆盘内随机选取一点（以下采用面积均匀分布）。令 \(D_1\) 为该点到圆心的距离，\(D_2\) 为该点到圆周的最短距离，\(D=\min(D_1,D_2)\)。求以厘米表示的 \(R\)，使 \(3\Pr(D\gt R)=\Pr(D\lt R)\)。

先补概念

圆盘中的均匀分布对应面积比例，不能把“到圆心的距离”直接当成均匀分布。半径为 \(r\) 的圆面积为 \(\pi r^2\)。本题全部换成厘米后，大圆半径为 200。

分步解答

1. 只用一个距离变量。设所选点到圆心的距离为 \(r\)，则 \(D_1=r\)、\(D_2=200-r\)，所以 \(D=\min(r,200-r)\)。这个较小值不可能超过 100。
2. 写出补事件。当 \(0\le R\le100\) 时，\(D\gt R\) 表示“离圆心超过 \(R\)，并且离圆周也超过 \(R\)”，也就是 \(R\lt r\lt200-R\)。这一部分是一个圆环。
3. 用面积计算。
   \[\Pr(D\gt R)=\frac{\pi(200-R)^2-\pi R^2}{\pi200^2}=1-\frac{R}{100}.\]
   边界圆周的面积为 0，所以 \(\Pr(D=R)=0\)，从而 \(\Pr(D\lt R)=R/100\)。
4. 代入题设。
   \[3\left(1-\frac R{100}\right)=\frac R{100}\quad\Longrightarrow\quad 4R=300\quad\Longrightarrow\quad R=75.\]
   此时较近距离小于 75 厘米的概率为 \(3/4\)，大于它的概率为 \(1/4\)，满足原等式。

易错点：若全程以米计算，会得到 \(0.75\) 米，提交前必须转换成 75 厘米。这里 \(D\) 恰好在 \([0,100]\) 上均匀分布，是面积相减后的结果；原始的半径 \(r\) 并不均匀。

原题 16 · Guests and Chairs：坐对椅子人数的方差

PDF 第 20 页 · 方法：指示变量、二阶矩、相关事件 · 难度：中等

完整题意：10 位客人随机坐到 10 把各有姓名牌的椅子上，每一种座位安排等可能。令 \(N\) 为恰好坐到自己椅子上的人数，求 \(N\) 的方差，按小数填写。

先补概念

指示变量只取 0 或 1：事件发生取 1，没有发生取 0。若发生概率为 \(p\)，它的期望就是 \(p\)。方差衡量随机变量偏离平均值的程度，可以用 \(\operatorname{Var}(N)=\mathbb E[N^2]-(\mathbb E[N])^2\) 计算。

分步解答

1. 把人数拆成十个指示变量。令 \(I_i=1\) 表示第 \(i\) 位客人坐对，否则为 0。则 \(N=I_1+\cdots+I_{10}\)。每位客人坐对的概率为 \(1/10\)，所以
   \[\mathbb E[N]=\sum_{i=1}^{10}\mathbb E[I_i]=10\times\frac1{10}=1.\]
2. 求两位指定客人同时坐对的概率。固定第一位坐对后，剩下 9 位客人在剩下 9 把椅子上仍随机排列。因此对于 \(i\ne j\)，
   \[\mathbb E[I_iI_j]=\Pr(I_i=1,I_j=1)=\frac1{10}\times\frac19=\frac1{90}.\]
3. 展开平方。因为 \(I_i^2=I_i\)，而十位客人共有 \(\binom{10}{2}=45\) 个无序对，
   \[\mathbb E[N^2]=\sum_i\mathbb E[I_i]+2\sum_{i\lt j}\mathbb E[I_iI_j]=1+2\times45\times\frac1{90}=2.\]
4. 代入方差公式。
   \[\operatorname{Var}(N)=2-1^2=1.\]

易错点：十个人是否坐对并不独立。一人坐对后，另一人坐对的条件概率从 \(1/10\) 变成 \(1/9\)。若误把 \(N\) 当成二项分布，会得到错误的 \(10\times0.1\times0.9=0.9\)。上述结论对任意 \(n\ge2\) 位客人都成立：坐对人数的期望和方差均为 1；\(n=1\) 时方差为 0。

原题 17 · Quadrilateral：随机切四段能否拼成四边形？

PDF 第 21 页 · 方法：几何可行条件、补事件、随机间距的对称性 · 难度：中等

完整题意：在长度为 1 的线段上，独立、均匀地选取三个切点，将线段分成四段。求这四段能够组成一个非退化四边形的概率。原题选项为 \(2/3\)、\(5/8\)、\(1/2\)、\(3/8\)、\(1/8\)。

先补概念

若要用几根线段首尾相接围成多边形，最长的一根必须短于其余线段的长度总和，否则其余线段拉直也接不上。反过来，对正长度的四条边，这个条件也足以组成非退化四边形。

分步解答

1. 将几何条件转成长度条件。记四段长为 \(L_1,L_2,L_3,L_4\)，总和是 1。最长的一段短于其余三段，等价于
   \[\max(L_1,L_2,L_3,L_4)\lt\frac12.\]
   因此只要计算“至少一段超过一半”的概率，再用 1 减去它。
2. 先算最左边一段超过一半。这等价于三个切点全部在 \((1/2,1)\) 内。三个切点独立，所以
   \[\Pr(L_1\gt1/2)=\left(\frac12\right)^3=\frac18.\]
3. 说明为什么其他三段也有相同概率。将切点排序为 \(u_1\lt u_2\lt u_3\) 后，四个间距为 \(u_1,u_2-u_1,u_3-u_2,1-u_3\)。所有非负且总和为 1 的间距组合，在对应的三维区域内具有相同密度；交换间距的位置不改变这个区域或密度。因此四段的边际分布相同，每段超过一半的概率都是 \(1/8\)。这叫随机间距的交换对称性，并不表示四个长度独立。
4. 相加时不需要减重叠。两段不可能同时严格大于 \(1/2\)，因为总长只有 1。因此四个失败事件互不相交，失败概率为 \(4/8=1/2\)。恰好等于一半的情况概率为 0。
5. 取补事件。
   \[\Pr(\text{能组成四边形})=1-4\times\frac18=\frac12.\]

易错点：不能把四段长度当成四个独立的均匀随机数，它们的和固定为 1。“一次独立选三个切点”与“每次选当前的一段再随机切开”的机制不同，后者一般不会得到本题答案。

原题 18 · Biased Coin：99% 胜率的游戏仍可能亏钱

PDF 第 22 页 · 方法：单次收益的加权平均、期望的线性性质 · 难度：基础

完整题意：一枚偏硬币出现正面的概率为 \(0.99\)。每出现一次正面获得 1 美元，出现一次反面损失 100 美元。投掷 3500 次后，期望财富是多少？原题要求填整数。

先补概念

期望是各种结果按发生概率加权后的平均值。胜率高并不自动代表平均赚钱，还必须同时考虑每次赢多少、输多少。若没有给出初始财富，能够确定的是净收益的期望；通常此类题把初始净财富记为 0。

分步解答

1. 写出一次投掷的两种收益。记单次净收益为 \(Y\)。它以概率 \(0.99\) 取 \(+1\)，以概率 \(0.01\) 取 \(-100\)。
2. 计算单次期望。
   \[\mathbb E[Y]=0.99\times1+0.01\times(-100)=0.99-1=-0.01\text{ 美元}.\]
   每局平均损失一美分。
3. 把 3500 次相加。令总净收益 \(T=Y_1+\cdots+Y_{3500}\)。利用期望的线性性质，
   \[\mathbb E[T]=3500\times(-0.01)=-35\text{ 美元}.\]
   这个求和步骤只需要每次的收益概率如题设，不依赖各次之间独立。
4. 用次数再检查一遍。正面次数的期望为 \(3500\times0.99=3465\)，反面次数的期望为 35，所以净收益期望为 \(3465-100\times35=-35\)。

易错点：不能把“99% 的投掷获利”理解成“整体有 99% 的概率获利”，也不能把 3500 次后的实际收益断言为 −35。实际反面次数会变化，−35 是反复进行整套实验后的平均净收益。题干没有设置破产停玩或资金约束，解答不额外加入这些规则。

原题 19 · Rudolph and the Grinch：方形池中的最少转向次数

PDF 第 23 页 · 方法：追及问题、最坏情况分析、先证下界再构造策略 · 难度：进阶

完整题意：Rudolph 落在一个正方形水池的中心，Grinch 在某一条边的中点。Rudolph 上岸后跑得比 Grinch 快，但 Grinch 的奔跑速度是 Rudolph 游泳速度的 4 倍。Rudolph 在游泳时最少需要改变多少次方向，才能保证逃脱？Rudolph 可以瞬间转向任意角度。

建模约定：按此类池边追赶题的标准解释，Grinch 只能沿池边移动，不能下水或横穿水池；双方都能观察对方的位置；Rudolph 必须严格先到岸，同时到达算被抓。没有这些约定，单靠题干中的速度信息不足以确定一个唯一追逃模型。

先补概念

“最少”需要两部分证明：先证明少于这个次数一定无法保证成功，再给出一个不论对方怎么跑都成功的策略。不能只举一个对手恰好跑错方向的例子。水中用直线距离，池边用沿正方形周界的距离，二者不能混用。

分步解答

1. 统一尺度。把水池设为 \([-1,1]\times[-1,1]\)，边长为 2，中心为 \(O=(0,0)\)。令游速为 1，则追赶速度为 4。初始 Grinch 在 \(G_0=(0,1)\)。整体放大水池或同比改变速度不会改变所需的转向次数。
2. 证明完全不转向无法保证逃脱。从中心直游到任何岸点，距离至少为 1，所以至少需要 1 单位时间。正方形周长为 8，Grinch 到任何岸点沿周界都能选较短的一路，路程至多为 4，所需时间至多为 1。因此一旦游泳方向固定，Grinch 可以提前或同时到达该方向的上岸点。故至少需要 1 次转向。
3. 先沿远离追赶者的方向游一小段。Rudolph 从 \((0,0)\) 直游到 \(P=(0,-0.1)\)，耗时 \(0.1\)。在这段时间内，Grinch 最多沿池边跑 \(0.4\)，还不足以到达顶边的任一角，所以此时必定在 \(G=(g,1)\)，其中 \(|g|\le0.4\)。这里允许 Grinch 提前改变方向或暂时不动。
4. 观察位置后确定上岸点。选择 \(E=(-g,-1)\)，即 Grinch 所在点沿正方形周界走半圈到达的对面点。从 \(G\) 沿左右两条路到 \(E\)，路程都恰好为 4，所以 Grinch 从此刻起无论怎么跑，最快也需要 1 单位时间。
5. 转向一次并直游上岸。Rudolph 从 \(P\) 到 \(E\) 的直线距离为
   \[PE=\sqrt{g^2+0.9^2}\le\sqrt{0.4^2+0.9^2}=\sqrt{0.97}\lt1.\]
   游速为 1，因此 Rudolph 严格早于 Grinch 到达 \(E\)，随后凭借更快的陆地速度逃脱。整个策略至多转向一次。

易错点：直接游向初始追赶者的正对面，双方恰好同时到达，不能保证逃脱。关键在于先移动一小段，再根据追赶者的当前位置选择最后的上岸点。证明中比较的是转向之后双方的剩余时间，不是把追赶者从最初位置重新计时。

原题 20 · Counting square：行列都递增的九宫格

PDF 第 24 页 · 方法：满足先后约束的计数、状态递推、标准杨表 · 难度：中等至进阶

完整题意：将整数 1 至 9 各使用一次，填入一个 \(3\times3\) 方格，要求每行从左向右严格递增，每列从上向下严格递增。共有多少种填法？

先补概念

先后约束指某些格子必须比另一些格子先填更小的数字。这里一个格子的上方和左方若有格子，就必须先填好。按 1、2、3、… 的顺序填，已经填好的部分一定从左上角连续排列：每行无空缺，上面的行不能比下面的行短。

分步解答：不依赖公式记忆的递推法

1. 用三个行长度表示状态。设已经填好的三行分别有 \(a,b,c\) 个格子，那么必须满足 \(3\ge a\ge b\ge c\ge0\)。令 \(F(a,b,c)\) 表示把最小的 \(a+b+c\) 个数字合法填入该形状的方法数。空格局只有一种，故 \(F(0,0,0)=1\)。
2. 考虑最后一个、也就是最大的数字放在哪里。它必须在某一行的最右端，而且下方不能还有已填格子。若第一行比第二行长，即 \(a\gt b\)，可从第一行删掉最后一个格子；第二行可删的条件是 \(b\gt c\)；第三行只要 \(c\gt0\) 就可删。
3. 把互不相同的最后一步相加。因此
   \[F(a,b,c)=\mathbf1_{a\gt b}F(a-1,b,c)+\mathbf1_{b\gt c}F(a,b-1,c)+\mathbf1_{c\gt0}F(a,b,c-1).\]
   这里 \(\mathbf1\) 表示条件成立才计入该项；条件不成立的项直接省略。例如 \(F(2,1,0)=F(1,1,0)+F(2,0,0)=1+1=2\)。
4. 按已填数字个数，从少到多计算。下表列出全部合法状态。括号后的数字是该状态的方法数，因此可以逐行按上式检查，而不需要列举 \(9!=362880\) 个全排列。

5. 读取最终状态。三行都填满就是 \((3,3,3)\)，因此答案为 \(F(3,3,3)=42\)。

进阶检查：钩长公式

行列严格递增、使用 1 至格子总数的这种填法称为标准杨表。其钩长公式为“总格子数的阶乘，除以各格子钩长的乘积”。某格的钩长等于它右边格子数、下方格子数，再加自身一个。此题九个钩长排列为

钩长公式在这里用于快速复核；前面的递推已经独立给出了完整计数，不要求初学者先记住这个定理。

易错点：先把每行排序，的确可得到 \(9!/(3!)^3\) 种行递增填法，但再除以 \((3!)^3\) 并不能处理列条件，因为两类约束相互影响。递推法的优势是每一步都只加入满足两类约束的填法，既不遗漏也不重复。

原题 21：均匀分布上界的最大似然估计偏差

原题标题：Maximum Likelihood Bias · PDF 第 25 页 · 方法：似然函数、最大值的分布、期望积分

完整题意。从区间 \([0,A]\) 上的均匀分布中独立抽取 10 个数，其中上界 \(A\) 未知。用最大似然法估计 \(A\)，求该估计的期望偏差占 \(A\) 的比例。题目要求把偏差按非负数填写，并用最简真分数作答。

先学概念

均匀分布表示等长区间有相同概率。最大似然估计的做法是：把已经观察到的数据固定，寻找让这组数据对应的概率密度最大的参数。偏差通常定义为“估计值的期望减去真实值”，所以偏差本身可以为负。本题额外要求非负，实际要填的是低估量的大小。

1. 找出参数不能小于哪个数。记样本最大值为 \(M=\max(X_1,\ldots,X_{10})\)。如果候选上界小于 \(M\)，它就不可能产生已经出现的样本，因此似然为 0。
2. 在允许的参数中比较似然。当候选值 \(a\ge M\) 时，每个观测的密度为 \(1/a\)，独立性使联合密度相乘，得到 \(L(a)=a^{-10}\)。这个量随 \(a\) 增大而减小，所以应取允许的最小值：\(\widehat A=M\)。
3. 计算最大值的分布。对 \(0\le m\le A\)，最大值不超过 \(m\)，等价于 10 个样本都不超过 \(m\)。因此
   \[P(M\le m)=\left(\frac mA\right)^{10},\qquad f_M(m)=\frac{10m^9}{A^{10}}.\]
   这里 \(f_M\) 是最大值的概率密度，由前面的分布函数求导得到。
4. 求期望并换成题目所要的比例。
   \[E[M]=\int_0^A m\frac{10m^9}{A^{10}}\,dm=\frac{10A}{11}.\]
   所以平均少估了 \(A-E[M]=A/11\)，再除以 \(A\)，得到 \(1/11\)。

易错点。样本最大值虽然是最大似然估计，但并非无偏估计。把它乘以 \(11/10\) 后，\(\widetilde A=11M/10\) 才满足 \(E[\widetilde A]=A\)。一般抽取 \(n\) 个数时，相对低估量是 \(1/(n+1)\)。

原题 22：抛物线与直线围成区域的重心

原题标题：Center of Mass · PDF 第 26 页 · 方法：几何概率、水平切片、加权平均

完整题意。在平面区域 \(x^2\le y\le1\) 中按面积均匀选择一点，求其纵坐标 \(Y\) 的期望，用最简真分数作答。

先学概念

按面积均匀选点，表示点落入某个小区域的概率等于“小区域面积除以总面积”。纵坐标落在哪个高度，还取决于该高度的区域有多宽。因此，平面上的均匀选点一般不会产生均匀分布的纵坐标。

1. 确定纵坐标范围。因为 \(x^2\ge0\)，所以 \(0\le y\le1\)。固定一个高度 \(y\)，条件 \(x^2\le y\) 给出 \(-\sqrt y\le x\le\sqrt y\)，这一横条的宽度是 \(2\sqrt y\)。
2. 求总面积。把每一条“宽度乘以微小高度”相加，也就是积分：
   \[S=\int_0^1 2\sqrt y\,dy=\frac43.\]
3. 写出高度的概率密度。高度在 \(y\) 附近、厚度为 \(dy\) 的横条面积约为 \(2\sqrt y\,dy\)，所以
   \[f_Y(y)=\frac{2\sqrt y}{4/3}=\frac32\sqrt y,\qquad 0\le y\le1.\]
4. 做按概率加权的平均。
   \[E[Y]=\int_0^1 y f_Y(y)\,dy=\frac32\int_0^1 y^{3/2}\,dy=\frac32\cdot\frac25=\frac35.\]

直观检查。较高处的横条更宽，随机点落在较高位置的机会更多，所以结果应大于 \(1/2\)。\(3/5\) 符合这一判断。不能直接把纵坐标范围的两个端点取平均。

原题 23：五枚硬币全部同面，店家能允许几轮？

原题标题：Quintuple Coin Perfection Game · PDF 第 27 页 · 方法：分状态讨论、条件概率、最优决策；题干存在重要缺项

完整题意。有 5 枚公平硬币。每一轮，玩家可以选择其中任意一些硬币重新投掷；当 5 枚硬币全部同面时玩家获胜。如果进行了 \(N\) 轮仍未全部同面，玩家失败。问店家最多能设置多少轮，使游戏仍对店家有利。给出的选项是 3、5、7、10、超过 10。

采用一组明确的规则进行完整计算

以下假定：第一轮投掷全部 5 枚硬币，并计入总轮数 \(N\)；随后玩家可以观察结果、保留部分硬币并重新投掷其余硬币；每次重投相互独立；玩家获胜赚 1、失败亏 1。于是店家有利等价于玩家胜率小于 \(1/2\)。这里的“投掷”会重新产生随机结果，不能理解为直接把已知的一面翻成另一面。

1. 第一轮后，只需区分三种状态。全部同面有 2 种结果，概率为 \(2/32=1/16\)；4 枚与 1 枚不同面有 \(2\binom51=10\) 种结果，概率为 \(5/16\)；3 枚与 2 枚不同面有 \(2\binom52=20\) 种结果，概率为 \(5/8\)。分母 32 来自 \(2^5\)，因为每枚硬币都有正反两种结果。
2. 只剩一轮时，最优做法是保留多数面。若是 4 比 1，只需重投那 1 枚，成功率为 \(1/2\)。若是 3 比 2，重投那 2 枚，成功率为 \(1/4\)。为什么这是最优？若有两种面都被保留下来，本轮必然无法同面；若只保留一种面，应保留数量较多的那种，从而让必须同时投对的硬币最少。
3. 计算两轮内的最大胜率。第一轮已经成功的结果直接计入，其他结果使用上一条的最优一轮策略：
   \[P(\text{两轮内成功})=\frac1{16}+\frac5{16}\cdot\frac12+\frac58\cdot\frac14=\frac38.\]
   \(3/8\lt1/2\)，所以总共允许两轮时，店家仍有利。
4. 证明允许三轮已经不行。在第一轮之后，继续保留多数面，哪个少数面投成多数面就将其保留。原来有 1 枚少数面时，两次机会内投对的概率为 \(1-(1/2)^2=3/4\)。原来有 2 枚少数面时，两枚都在两次机会内投对的概率为 \((3/4)^2=9/16\)。这样可达到
   \[P(\text{三轮内成功})\ge\frac1{16}+\frac5{16}\cdot\frac34+\frac58\cdot\frac9{16}=\frac{83}{128}\approx0.64844.\]
   这个策略已经让玩家胜率超过 \(1/2\)。允许更多轮不会降低玩家的成功机会，所以最大轮数只能是 2。对全部可选子集逐一做有限状态递推，也得到三轮的最优胜率恰为 \(83/128\)。

为什么有人会得到选项 10？

如果另外规定“每一轮必须重新投全部 5 枚”，单轮成功率才始终是 \(1/16\)。此时 \(N\) 轮内成功概率为 \(1-(15/16)^N\)，比较 \(1/2\) 后可得最大 \(N=10\)。这条计算本身正确，但它忽略了原题允许选择子集重投的规则。不能把它直接用于本题。

易错点。平均需要多少轮，与给定轮数内的胜率，是两个不同问题；不能把平均完成轮数向下取整当作店家有利的轮数。另外，如果参与费为 \(c\)、成功时领取总奖金 \(w\)，店家的盈利条件是成功概率小于 \(c/w\)，阈值未必是 \(1/2\)。

原题 24：利益相同的两位玩家如何决定是否继续？

原题标题：Aligned Priorities Game · PDF 第 28 页 · 方法：阈值策略、离散计数、共同收益最优化

完整题意。一副牌包含标号 1 到 100 的 100 张不同牌。A、B 各随机抽取一张，只看自己的牌，然后分别决定放弃还是继续。任意一人放弃，两人都得到 0；两人都继续时，若 A 的数字较大，两人各得 1；若 B 的数字较大，两人各得 −1。求双方采用最优策略时各自的期望收益，填写最简真分数。

必要解释。以下按同一副牌无放回抽取、两人同时决策、决策前不交换牌面信息理解。因此牌面不会相同，一共有 \(100\times99=9900\) 个等可能的有序结果。双方利益相同，都希望 A 的牌较大。这里的最优指共同收益最大的策略组合。

先学概念：阈值策略

阈值策略是用一个分界数字做决定，例如 A 只在牌面至少为 34 时继续。对本题而言，A 的牌越大，继续越有利；B 的牌越小，继续越有利。这种单调性可以把大量复杂策略简化成两个整数阈值。

1. 为什么只研究阈值就够了？先固定 B 的策略。A 拿到某张牌后，继续的收益取决于“B 会继续且比自己小的牌有多少”，减去“B 会继续且比自己大的牌有多少”。A 的数字增大时，这个差值不会下降。因此 A 的最优选择可以写成“足够大就继续”。同理，固定 A 后，B 可以写成“足够小就继续”。随机化也不能增加全局最大值：固定对方后，自己的继续概率对应的收益是线性的，取继续或放弃的端点就能达到最优。
2. 用两个数量表示阈值。设 A 继续的牌是最大的 \(m\) 张，B 继续的牌是最小的 \(k\) 张。两人都继续的数字组合共有 \(mk\) 个。如果两个区间有交集，记交集长度为 \(r=m+k-100\)。交集中有 \(r\) 对“数字相等”的组合，但它们不可能从同一副牌抽出。
3. 数清胜局和负局。若区间交叠，负局只能来自交集中 B 大于 A 的两张牌，所以有 \(\binom r2=r(r-1)/2\) 个。把相同数字排除后，真实的继续组合有 \(mk-r\) 个。因此“胜局数减负局数”为
   \[(mk-r)-2\binom r2=mk-r^2.\]
   若区间不交叠，所有继续组合都赢，此时直接用 \(mk\)。
4. 证明净胜局数最多为 3333。不交叠时 \(m+k\le100\)，所以 \(mk\le2500\)。交叠时设 \(s=m+k\)，由 \((m-k)^2\ge0\) 得 \(mk\le s^2/4\)。于是
   \[mk-(s-100)^2\le\frac{s^2}{4}-(s-100)^2=\frac{10000}{3}-\frac34\left(s-\frac{400}{3}\right)^2\le\frac{10000}{3}.\]
   净胜局数必须是整数，因此至多为 3333。
5. 给出达到上界的实际策略。让 A 在牌面至少为 34 时继续，让 B 在牌面至多为 67 时继续。此时 \(m=k=67\)，交叠牌为 34 到 67，共 \(r=34\) 张，所以净胜局数为 \(67^2-34^2=3333\)。具体胜局 3894 个，负局 561 个，相差正好 3333。其余结果收益为 0。
6. 除以全部可能结果。
   \[E[\text{每位玩家的收益}]=\frac{3894-561}{9900}=\frac{3333}{9900}=\frac{101}{300}.\]

易错点与边界。不能要求两人都拿大牌才继续，因为 B 的小牌有利于两人获利。把牌面近似成连续均匀数会得到 \(1/3\)，但那是近似题的答案。若改成两副牌独立抽取，还必须说明相同数字如何计收益；若相同数字计 0，分母会变为 10000，结果为 \(3333/10000\)。原题没有描述这种独立抽取机制。

原题 25：到直角三角形斜边的距离最大

原题标题：Point in the Triangle · PDF 第 29 页 · 方法：坐标法、点到直线距离、区域面积比

完整题意。三角形 \(ABC\) 的边长为 \(AB=45\)、\(AC=60\)、\(BC=75\)。在内部按面积均匀选择一点 \(D\)。求：该点到三条边的垂直距离中，到 \(BC\) 的距离最大，这件事发生的概率。用最简真分数作答。

先学概念

这里的距离是点到边所在直线的垂直距离。均匀选点使问题转化为面积比：先找出满足两个距离不等式的区域，再用它的面积除以三角形面积。恰好两个距离相等的点在若干线段上，面积为 0，不影响概率。

1. 建立方便的坐标。因为 \(45^2+60^2=75^2\)，这是直角三角形。取 \(A=(0,0)\)、\(B=(45,0)\)、\(C=(0,60)\)。设随机点为 \(D=(x,y)\)，则到两条直角边的距离分别为 \(y\) 和 \(x\)。
2. 写出到斜边的距离。斜边方程为 \(4x+3y=180\)。点到直线 \(ax+by+c=0\) 的距离是 \(|ax+by+c|/\sqrt{a^2+b^2}\)。三角形内部有 \(4x+3y\le180\)，所以到 \(BC\) 的距离为 \((180-4x-3y)/5\)。
3. 把“斜边距离最大”改写成区域条件。
   \[\frac{180-4x-3y}{5}\ge x,\qquad\frac{180-4x-3y}{5}\ge y.\]
   化简后得到 \(3x+y\le60\)、\(x+2y\le45\)，再加上 \(x\ge0,y\ge0\)。这些条件已保证点在原三角形内。
4. 找出可行区域的顶点。在横轴上最远到 \((20,0)\)，在纵轴上最远到 \((0,45/2)\)。联立 \(3x+y=60\)、\(x+2y=45\)，解得交点 \((15,15)\)。因此所求区域是四边形
   \[(0,0),\quad(20,0),\quad(15,15),\quad(0,45/2).\]
5. 分成两个三角形求面积。从原点连接 \((15,15)\)，两块面积分别为 \(20\times15/2=150\) 和 \((45/2)\times15/2=675/4\)，合计 \(1275/4\)。原三角形面积是 \(45\times60/2=1350\)。

易错点。到三条边的距离并不具有对称性，不能直接答 \(1/3\)。本题三条边长度不同，三种“哪一条边最远”的区域面积也不同。

原题 26：猫在 21 栋房屋之间随机行走

原题标题：Street Cat · PDF 第 30 页 · 方法：马尔可夫链、奇偶性、有限步概率递推

完整题意。21 栋房屋排成一行，依次编号 1 到 21。猫在第 0 天位于 1 号房。每天早上，它从当前房屋的相邻房屋中等概率选择一个并走过去；在两端只有一个邻居，所以必须向内走。求第 1000 天它位于 1 号房的概率，最多保留三位小数。

先学概念

下一步只取决于当前房屋，不取决于更早的路线，这种随机过程称为马尔可夫链。一个关键问题是：猫每次都要移动一步，所以房屋编号的奇偶性每一天都会改变。

1. 先检查能够到达哪些位置。从奇数号 1 出发，第 1 天只能在偶数号，第 2 天只能在奇数号。第 1000 天为偶数天，因此猫只可能在 1、3、5、……、21 这些奇数号房屋。不能把全部 21 栋房屋当成等可能。
2. 求不随一步转移而变化的分布。内侧房屋有两个邻居，两端房屋只有一个。设两端的概率为 \(c\)，其余 19 栋的概率为 \(2c\)，则每条相邻边上向左和向右转移的概率都相等，所以这个分布经过一天后保持不变。总和为 \(2c+19\times2c=40c=1\)，得到两端概率 \(1/40\)，内侧概率 \(1/20\)。这叫平稳分布。
3. 处理奇偶性，不能直接拿平稳分布作答。从 1 号出发的概率分布每天在奇、偶两组之间交替，并不会按天收敛到上一条的整体分布。只观察偶数天，长期分布等于把平稳分布限制在奇数号房屋上，再归一化。奇数号房屋的平稳概率合计是 \(1/2\)，因此偶数天回到端点的概率趋近于 \((1/40)/(1/2)=1/20=0.05\)。
4. 有限的 1000 天需要再核对精度。记 \(p_t(j)\) 为第 \(t\) 天在 \(j\) 号的概率，初值为 \(p_0(1)=1\)，其他为 0。每一步将端点的全部概率送到唯一邻居，将内侧房屋的概率各分一半送给左右邻居。重复 1000 次可得
   \[p_{1000}(1)=0.05000041679938077\ldots.\]
   这个值略大于 0.05，但保留三位小数仍是 0.050。这里已经计算了有限步概率，未把极限值当作精确等式。

p = [1.0] + [0.0] * 20
for day in range(1000):
    q = [0.0] * 21
    q[1] += p[0]
    q[19] += p[20]
    for i in range(1, 20):
        q[i - 1] += p[i] / 2
        q[i + 1] += p[i] / 2
    p = q
print(p[0])

易错点。\(1/21\) 忽略了端点与内部房屋的不同；\(1/40\) 忽略了奇偶周期；\(1/11\) 虽然注意到了奇数号房屋，却仍错误地假定它们等可能。若问第 999 天，则答案严格为 0。

原题 27：四个侧面重心构成的新棱锥体积

原题标题：Pyramid · PDF 第 31 页 · 方法：重心坐标、平面面积、棱锥体积

完整题意。一个四棱锥的底面是边长 24 米的正方形，高为 20 米。取四个三角形侧面的重心，以及原底面的中心。这五个点构成一个倒置的四棱锥。求新四棱锥的体积，只填写以立方米为单位的整数部分。

先学概念

三角形重心是三条中线的交点，它的坐标等于三个顶点坐标的平均值。棱锥体积为“底面积乘以高，再除以 3”。这里原题只说底面为正方形，没有要求原顶点恰好位于底面中心上方；以下计算也不需要添加这一条件。

1. 设置坐标。把底面放在 \(z=0\) 平面，中心设为原点，四个顶点为 \((\pm12,\pm12,0)\)。允许棱锥顶点在任意水平位置，写成 \(S=(u,v,20)\)。
2. 分别对每个侧面的三个顶点取平均。四个侧面重心为
   \[\left(\frac u3,\frac v3-8,\frac{20}3\right),\quad\left(\frac u3+8,\frac v3,\frac{20}3\right),\quad\left(\frac u3,\frac v3+8,\frac{20}3\right),\quad\left(\frac u3-8,\frac v3,\frac{20}3\right).\]
   四点都位于同一高度 \(z=20/3\)，形成新棱锥的底面。
3. 求这个新底面的面积。忽略共同的水平平移 \((u/3,v/3)\)，四个点就是 \((0,-8),(8,0),(0,8),(-8,0)\)。它们形成正方形，两条对角线均为 16，所以面积为 \(16\times16/2=128\) 平方米。
4. 求新棱锥的高与体积。新顶点是原底面中心 \((0,0,0)\)，到新底面平面 \(z=20/3\) 的垂直距离为 \(20/3\)。所以
   \[V=\frac13\times128\times\frac{20}3=\frac{2560}{9}=284.444\ldots\text{ 立方米}.\]

易错点。新底面的边长是 \(8\sqrt2\)，不是 16；16 是对角线长度。原题要求取整数部分，不能把体积填成 285。顶点的水平位置 \((u,v)\) 只会整体平移新底面，不会改变它的面积或新棱锥的高。

原题 28：四个互不相同的数，方差最大是多少？

原题标题：Maximal Variance · PDF 第 32 页 · 方法：方差恒等式、上界与达到条件；需要区分方差口径

完整题意。从 1、2、……、10 中不重复地抽取 4 个数，问这 4 个数可能达到的最大方差，结果保留两位小数。

先说明口径。如果把抽到的 4 个数视为一个数据集合，其方差通常用平方偏差之和除以 4。若题目指通常的样本方差，则分母为 \(4-1=3\)。原题没有明确分母，下面分别给出两个答案；主解按“这 4 个数的方差”采用分母 4。

先学概念

方差衡量各个数距离平均值的离散程度：距离越大，平方偏差越大。不过，换一个数也会改变平均值，所以仅凭“选最两端的数”这一感觉还不能完成证明。下面用一个固定中心构造严格上界。

1. 先给出可能的最优选择。从两端各选两个数，得到 \(1,2,9,10\)，平均值是 \(5.5\)。平方偏差之和为
   \[(1-5.5)^2+(2-5.5)^2+(9-5.5)^2+(10-5.5)^2=20.25+12.25+12.25+20.25=65.\]
   因此分母为 4 的方差是 \(65/4=16.25\)。
2. 证明任意选择都不会更大。设任意四个数的平均值为 \(\bar x\)，以固定中心 \(c=5.5\) 展开平方，可得
   \[\frac14\sum_{i=1}^4(x_i-\bar x)^2=\frac14\sum_{i=1}^4(x_i-5.5)^2-(\bar x-5.5)^2\le\frac14\sum_{i=1}^4(x_i-5.5)^2.\]
   最后减去的是平方数，不会为负。这说明相对于真实平均值的方差，不超过相对于固定中心 5.5 的平均平方距离。
3. 利用“不重复”限制。在 1 到 10 中，距离 5.5 最远的四个不同数恰好是 1、10、2、9。它们的平方距离总和为 65，所以任意四个不同数的右侧上界都不超过 \(65/4\)。而第一步所选的四个数平均值就是 5.5，减掉的平方为 0，确实达到上界。
4. 如采用分母 3，则只需更换分母。同一组数仍然最优，因为所有候选组合都乘了同一个比例 \(4/3\)。此时最大样本方差为 \(65/3=21.666\ldots\)。

易错点。“随机抽取”描述产生样本的方式，本题问的是所有可能样本中的最大值，不是方差的期望。不能重复选 \(1,1,10,10\)，因为原题禁止重复。

原题 29：双层排序代码一共做了多少次比较？

原题标题：Bubble sort · PDF 第 33 页 · 方法：逐层循环计数、区分元素比较与条件判断

完整题意。对一个含 10 个元素、严格递减排列的数组执行下面代码，问总共需要多少次比较。原题选项为 55、90、111、101。

for (int i = 0; i < 10; ++i) {
    for (int j = i + 1; j < 10; ++j) {
        if (arr[i] < arr[j]) {
            double t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    }
}

先学概念

“比较次数”有两种常见口径：排序分析常只数数组元素之间的比较；逐句分析代码时，也可能把循环条件中的整数比较计入。原题选项没有 45，却有 111，因此选项对应的是把所有比较运算都计入的口径。解题时应把这一区别说清楚。

1. 数数组元素比较。当 \(i=0\) 时，\(j\) 取 1 到 9，共 9 次；\(i=1\) 时为 8 次，依次递减；\(i=9\) 时为 0 次。因此 arr[i] < arr[j] 共执行
   \[9+8+\cdots+1+0=\frac{9\times10}{2}=45\text{ 次}.\]
2. 数内层循环的条件比较。每次内层循环结束，还要多进行一次失败的 j < 10 检查。例如 \(i=0\) 时，执行循环体 9 次，检查条件 10 次；\(i=9\) 时，循环体 0 次，仍检查条件 1 次。合计
   \[10+9+\cdots+2+1=55\text{ 次}.\]
3. 数外层循环的条件比较。i < 10 在 \(i=0,1,\ldots,9\) 时各成功一次，又在 \(i=10\) 时失败一次，共 11 次。
4. 相加。代码中的比较总次数为 \(45+55+11=111\)。数组原本严格递减，使每个 if 条件都为假，因此交换次数为 0；但该比较仍必须执行，两个循环也不会提前停止。

易错点。不能把“无需交换”理解为“无需比较”。也不要只凭题目标题套用带提前终止标记的冒泡排序结论；应分析实际给出的循环边界与停止条件。

原题 30：买卖双方都能用代金券，最小无法支付金额是多少？

原题标题：Coupon Exchange · PDF 第 34 页 · 方法：带符号表示、平衡三进制、连续可达区间

完整题意。买家和卖家各持有 5 张代金券，面额分别为 1、3、9、27、81，每种面额各一张。买家用若干张付款，卖家可以用自己的券找零。例如价格为 5 时，可以付 9，找回 3 和 1。求双方无法完成交易的最小正整数价格。

先学概念

每一种面额对卖家最终收到的净金额有三种作用：买家支付一张，记作 \(+1\) 倍；卖家找回一张，记作 \(-1\) 倍；双方都不用，记作 0 倍。如果双方同时交换同额券，净效果仍然是 0。用 \(-1,0,1\) 作数字、以 3 的幂作位权的表示称为平衡三进制。

1. 把交易写成数学式。所有可以完成的净支付都具有形式
   \[x=c_0+3c_1+9c_2+27c_3+81c_4,\qquad c_i\in\{-1,0,1\}.\]
   正系数由买家支付，负系数由卖家找零，所以每一种这样的表示都能落实成一次合法交易。
2. 先找最大可能支付。买家的券全部支付、卖家不找零时，净额最大，为 \(1+3+9+27+81=121\)。因此 122 一定不能支付，但还需要证明 1 到 121 中没有更早的缺口。
3. 证明可表示金额没有缺口。令 \(d_i=c_i+1\)，则每个 \(d_i\) 都属于 \(\{0,1,2\}\)，并且
   \[x+121=d_0+3d_1+9d_2+27d_3+81d_4.\]
   右侧就是普通的五位三进制，可以表示从 0 到 \(3^5-1=242\) 的每个整数。因此 \(x\) 可以表示从 −121 到 121 的每个整数，特别包括全部正整数 1 到 121。
4. 用小例子理解“找零填补缺口”。只有 1 面额时，净额可为 −1、0、1；再加入面额 3，三个区间分别是 \([-4,-2]\)、\([-1,1]\)、\([2,4]\)，正好连成全部整数 −4 到 4。随后加入 9、27、81，同样把连续范围依次扩展到 −13 至 13、−40 至 40、−121 至 121。

易错点。不能把买卖双方的券都当成买家的支付能力，从而把上界写成 242。卖家的券用于找零，会减少净支付。只算买家能直接凑出的子集和也不够，因为例如 \(2=3-1\)、\(5=9-3-1\) 都依赖找零。