小红书量化面试题库 3–54：52 道题的完整推导与面试方法

第3题：圆排列相邻差之和为16

完整题面：将整数1～9随机排列在一个圆圈上，求所有相邻两个数的差的绝对值之和等于16的概率。

答案：\(1/315\)。

概念补课：“绝对值之和”可以看成沿圆周走一圈的总路程。因为最后回到起点，整圈向上走了多少，向下就一定走了多少；这就是“总上升量＝总下降量”。

先识别模型

这是一个“总变差达到下界”的圆排列问题。闭合路径中的总上升量必须等于总下降量，而1和9的跨度给出不可突破的最低成本。

逐步推导

1. 把顺时针相邻差分成上升和下降两类。因为绕一圈回到原点，两类绝对值总和相等。
2. 从1到9至少要上升8，再从9回到1至少下降8，所以总和至少16。
3. 若总和恰好16，不能有任何额外折返；从1到9的两个方向都必须严格递增。
4. 固定1的位置后，2到8分别选择放在两条单调链上，共2⁷种；恢复1在9个位置，合格数为9×2⁷。
5. 除以9!得到1/315。

推导补全：把关键一步展开

1. 为什么两条链都必须单调？把圆分为从1到9的两条路径，每条路径总变差至少9−1=8；只要某条中间先降后升，就在8之外增加两倍的回撤。总和达到16恰好要求两条都没有回撤。
2. 计数中的2⁷不是在任意安排顺序。每个中间数只选择属于哪条链，链内顺序由单调性唯一确定。于是分配与合格排列一一对应；9×128/362880=1/315。

易错点与面试表达

圆周旋转是否算同一排列要先说清。这里按题目“随机排列”把9个位置区分，因此分子分母都保留位置因子。

第4题：循环赔率是否有正期望下注

完整题面：三支球队A、B、C比赛，AB、BC、CA的赔率均为1.5:3。球队实力值为正、固定且未知；实力为a、b的两队比赛胜率分别为a/(a+b)、b/(a+b)。是否存在期望为正的下注策略？

答案：存在。对AB押B、对BC押C、对CA押A，各下注1元，合计期望利润严格为正。

概念补课：本题按十进制赔率理解“赔率3”：下注1元，赢时总共拿回3元（包含本金），净赚2元；输时亏掉这1元。若胜率为p，平均净利润是\(p\times 2+(1-p)\times (-1)=3p-1\)，所以赔率3的下注只要真实胜率超过1/3，就有正期望。期望是按概率加权的平均收益，不保证单次赢钱。

先识别模型

赔率3的一方按题目顺序是B、C、A，对应的真实胜率为\(b/(a+b)\)、\(c/(b+c)\)、\(a/(c+a)\)。这三场的“押谁”形成循环：B胜A、C胜B、A胜C。我们不知道a、b、c的数值，但可以比较三笔下注的总期望；策略不需要先猜哪支队最强。

逐步推导

1. 赔率为3的一笔下注，胜率记作\(p\)，期望净利润为\(3p-1\)。三场各下注1元，总期望就是三笔期望相加。
2. 把三场押中一方的胜率记作\(S=b/(a+b)+c/(b+c)+a/(c+a)\)，于是总期望为\(3S-3\)。现在只需证明\(S>1\)。
3. 因为第三支球队的实力也为正，\(a+b<a+b+c\)，所以\(b/(a+b)>b/(a+b+c)\)。同理，\(c/(b+c)>c/(a+b+c)\)，\(a/(c+a)>a/(a+b+c)\)。三条相加，右边恰好是\((a+b+c)/(a+b+c)=1\)，故\(S>1\)。
4. 因此三场各下注1元的总期望净利润为\((3p_{1}-1)+(3p_{2}-1)+(3p_{3}-1)=3(S-1)>0\)。
5. 例如\(a=9,b=3,c=1\)时，三笔期望分别为\(-0.25\)、\(-0.25\)、\(1.7\)元，总和为\(1.2\)元。这说明结论是“三笔合计为正”，不是“每一笔都为正”。

推导补全：把关键一步展开

1. 逐笔净收益可写成3I−1，I为是否押中的指标。总收益3(I₁+I₂+I₃)−3，所以期望只涉及三个边际胜率，不必建立比赛之间的联合分布。
2. 实力相等时三笔胜率各1/2，总期望3×(3/2)−3=1.5元。实力悬殊时其中两笔可能亏期望，不能把合计优势解释为已知每场哪边都有优势。

易错点与面试表达

“1.5:3”可能采用不同赔率口径；这里按十进制赔率3计算。概率加权的期望可以直接相加，不要求三场比赛独立。现实下注还会受到抽水、限额和资金风险影响，本题只比较理想模型下的期望利润。

第5题：布朗运动在(1,2)内有无穷多个零点

完整题面：求一维标准布朗运动在时间区间(1,2)内有无穷多个零点的概率。

答案：\(1/2\)。

概念补课：把布朗运动想成一个在数轴上不停随机左右移动的点，\(W_{t}\)表示它在时刻t的位置，且\(W_{0}=0\)。路径连续，所以从正数走到负数必经过0；但路径很粗糙，在任意小的时间尺度上仍会上下波动。“标准”表示没有左右偏好，并且一单位时间的位移服从标准正态分布。\(\Phi (z)\)表示标准正态随机变量不超过z的概率，例如\(\Phi (0)=1/2\)。

先识别模型

题目中的(1,2)是时间范围；“零点”是满足\(W_{t}=0\)的时刻。先求这段时间里是否至少碰到一次0。布朗运动有局部振荡性质：从0出发后，在每个任意短的时间段里，几乎必然既到过正位置也到过负位置。第一次碰到0之后，后续过程又像一段从0出发的新布朗运动，因此零点会在附近无穷聚集。若零点只有有限个，路径在最后一个零点之后就必须固定在0的一侧；这与“任意短时间里两侧都会到达”矛盾。普通连续曲线并不一定有这个性质；这里用到的是布朗运动的局部振荡定理。于是本题的概率等于“在(1,2)内至少碰到一次0”的概率。

逐步推导

1. 设第1秒的位置是\(W_{1}=x\)。从第1秒往后的一单位时间，是一段从x开始的新布朗运动。记这一段的位移为\(Y\)，则\(Y\)服从标准正态分布，且与第1秒以前独立；第2秒的位置是\(x+Y\)。
2. 先看\(x>0\)。若终点\(x+Y<0\)，连续路径一定在途中碰到0。终点落到负侧的概率是\(P(Y<-x)=\Phi (-x)\)。但有些路径碰到0后又回到正侧；把路径第一次碰到0之后的部分关于0镜像翻转，会把这些路径一一对应到终点在负侧的路径，且概率相同。因此总击中概率是\(2\Phi (-x)\)。从负侧出发用对称性处理，合并为\(2\Phi (-|x|)\)。
3. 这解释了图片里的公式：起点离0越远，\(\Phi (-|x|)\)越小；乘2是因为“碰到后又回到起点同侧”的路径也要算进去。给定\(W_{1}\)时，击中概率是\(2\Phi (-|W_{1}|)\)，对所有可能的第1秒位置取平均，总概率为\(E[2\Phi (-|W_{1}|)]\)。这里\(E\)表示按\(W_{1}\)的概率分布加权平均。
4. 令\(X=W_{1}\)，\(Y=W_{2}-W_{1}\)。X、Y相互独立，且都服从标准正态分布。按\(\Phi \)的定义，\(E[\Phi (-|X|)]=P(Y\le -|X|)\)：事件就是Y为负，并且\(|Y|\ge |X|\)。
5. X、Y同分布且独立，所以谁的绝对值更大，各占一半，\(P(|Y|>|X|)=1/2\)；Y正负对称，因此再乘\(1/2\)，得到\(P(Y\le -|X|)=1/4\)。所以总击中概率为\(2\times 1/4=1/2\)。

推导补全：把关键一步展开

1. 把最后一步的平均也展开：令X、Y独立标准正态，则E[2Φ(−|X|)]=2P(Y≤−|X|)。平面上Y≤−|X|是向下的90度扇形，二维标准正态旋转对称，所以概率为1/4，再乘2得1/2。
2. 只在区间终点t=2才第一次碰零的概率为0；若在内部首次击中零，强马尔可夫性保证余下任意正时间内零点会聚集。因此“至少一次”与“无穷次”的概率相同，而不是对所有连续过程都成立。

易错点与面试表达

只看\(W_{1}\)与\(W_{2}\)是否异号，只数到了“端点在两侧”的路径；路径可能中间碰到0、最后又回到原侧，反射原理负责把这部分补齐。开区间端点恰好为0的概率为0，不影响答案。自测所需的起点为1时，直接代入得\(2\Phi (-1)\approx 0.3174\)，约为31.7%。

第6题：10、22、33不能表示的最大整数

完整题面：不能写成若干个非负整数10、22、33之和的最大整数是多少？

答案：111。

概念补课：把10、22、33想成三种面额的硬币。“能表示N”就是能否凑出N元：\(N=10a+22b+33c\)，其中\(a,b,c=0,1,2,\ldots \)，分别是硬币数量。负数个或半个硬币都不允许。“互质”表示两个整数没有大于1的公因数。下面出现的Frobenius公式只适用于两个互质面额，不是直接拿来套三个数。

先识别模型

10、22都是偶数，33是奇数。并且\(2\times 33=3\times 22=66\)，因此每两个33可以换成三个22。奇数总额必须使用奇数个33；成对替换后，判断时只需保留一个33。偶数总额则只由10和22构成。

逐步推导

1. 若偶数\(N\)写成\(10a+22b\)，除以2后就是\(N/2=5a+11b\)。所以先找用5和11凑不出的最大整数。
2. 把整数按除以5的余数分成0、1、2、3、4五类。用11分别作为起点，可以得到每类最小的可表示数：\(0,11,22,33,44\)。在每一类里再不断加5，后面的数都可表示。每个起点之前最近的同余数缺口是\(\text{起点}-5\)，即\(-5,6,17,28,39\)；最大的是39。因此5和11的最大不可表示数为39，偶数部分对应的最大不可表示偶数为\(2\times 39=78\)。
3. 奇数表示必须使用奇数个33。每多出两个33，都能换成三个22，所以判断奇数\(N\)能否表示，只需拿出一个33，看剩余的\(N-33\)能否由10、22表示。于是最大的奇数失败值是\(33+78=111\)。
4. \(111\)确实不能表示，因为那会要求\(78\)能由10、22表示，而除以2后相当于用5、11凑39，已知39不可表示。任何大于111的偶数都大于78，能由10、22凑出；任何大于111的奇数减去33后也大于78，同样能凑出。因此111是全体整数中的最大失败值。紧邻的两个数也能看到覆盖开始：\(112=9\times 10+22\)，\(113=8\times 10+33\)。

Frobenius公式 \(pq-p-q\) 从哪里来？

对于两个大于1且互质的面额\(p\)和\(q\)，公式说最大的凑不出金额是\(pq-p-q\)。以5和11为例：任何数除以5的余数只有0至4；每多加一枚11，余数增加1，因此0、11、22、33、44分别成为五类金额的第一个“起点”。同一类之后每加5就仍在该类，所以起点及其后续都能凑出。最晚开始的一类从44开始，它前一个同类数是\(44-5=39\)，这就是最大缺口。

一般地，互质保证\(0q,1q,\ldots ,(p-1)q\)除以\(p\)的余数各不相同，正好覆盖全部p类：若两个余数相同，p会整除\((b-b')q\)；因为p、q互质且\(|b-b'|<p\)，只能是\(b=b'\)。任意表示里若用了p枚q币，可换成q枚p币，所以每一类最早的表示可把q的数量缩到0至p−1之间，正好是某个\(bq\)；此后每加p仍能表示。最后一类起点是\((p-1)q\)，它之前最近的同类数为\((p-1)q-p=pq-p-q\)，而它确实凑不出：它的余数要求至少用\(p-1\)枚q币，金额已达\((p-1)q\)，比目标多p。对任意更大的n，取与n同余的起点\(bq\)，则\(n-bq\)是大于−p的p的倍数，只能是非负数，因此n可表示。这就证明了公式给出的数凑不出，而所有更大的数都凑得出。若p、q不互质，余数不会覆盖全部类别，通常会有无穷多个数凑不出来，不能使用这个公式。

推导补全：把关键一步展开

1. 余数法为什么完整？11与5互质，所以0、11、22、33、44分别覆盖五个余数；在相同余数中，再加5总能继续表示。每类仅需检查最小起点之前的那个整数，最大缺口为44−5=39。
2. 用奇偶性把三面额问题降到两面额后，要分别证明111不可表示和所有更大的数可表示。只展示112、113的构造是示例，不足以单独证明其后全部覆盖；完整性由同余类加5的论证提供。

易错点与面试表达

不要把二元Frobenius公式直接套在10、22、33三个面额上。关键是先利用奇偶性和\(2\times 33=3\times 22\)的替换关系，把问题拆成两个互质数5、11；还必须同时证明111凑不出、所有更大的数都能凑出。

第7题：6个矩形最多分几块

完整题面：6个矩形最多能将平面划分为几个区域？

答案：122。

概念补课：一条新闭合曲线若与旧图形有m个互异交点，就被切成m段；每段把一个旧区域一分为二，所以区域数增加m。

先识别模型

这是“每加入一条曲线，边界被切成多少段就增加多少区域”的分割递推。

逐步推导

1. 两个矩形边界最多有8个交点。
2. 第k个矩形与前面k−1个矩形最多产生8(k−1)个互异交点。
3. 这些交点把新矩形边界切成8(k−1)段，每段穿过一个旧区域并把它一分为二。
4. R₁=2，故R₆=2+8(1+2+3+4+5)=122。

推导补全：把关键一步展开

1. 先证明上界：一条矩形边所在直线穿过另一个凸矩形至多有两个边界交点，四条边合计至多8个。k≥2时，在既有边界连通的配置中，若新增边界有m个互异横截交点，它是一条被切成m段的闭曲线，区域增加m；没有交点时另作增加1处理。下面的两两相交构造保证既有边界连通。
2. 上界还须可达：取中心重合、边长相同且转角各不相同的正方形，任意一对可产生8个横截交点，再轻微平移避开三重交点；有限多个横截交点在足够小扰动下仍存在。于是2+8×15=122确是最大值。

易错点与面试表达

122需要一般位置：不能相切、不能三条边界共点，也不能让交点重合。

第8题：5×5网格中心蚂蚁到边界

完整题面：位于5×5网格中心的蚂蚁，每次等可能向上、下、左、右走一格，走到边界停止，平均走几格？

答案：4.5步。

概念补课：“从某位置出发还要走几步”的期望满足首步分析：先固定付出1步，再对下一位置的剩余期望取平均。对称位置期望相同，因此9个内部格只需分三类。

先识别模型

有限网格上的吸收随机游走，最重要的技巧是按对称性压缩状态，而不是给25个位置逐个列方程。

逐步推导

1. 设中心、轴向相邻、斜向相邻三类期望步数分别为x、y、z。
2. 中心走一步必到轴向点：x=1+y。
3. 轴向点四个方向通向边界、中心、两个斜向点：y=1+(x+2z)/4。
4. 斜向点两个方向出界、两个方向到轴向点：z=1+y/2。
5. 代入前两式得\(y=1+[1+y+2(1+y/2)]/4=7/4+y/2\)，所以\(y=7/2\)，最终\(x=1+y=9/2\)。

推导补全：把关键一步展开

1. 把内部3×3点画成中心1个、轴向4个、斜向4个。轴向点如(1,0)的四个后继是(2,0)边界、(0,0)中心、(1,1)与(1,−1)斜向；斜向点有两个边界后继，故方程里的系数分别是1/4与2/4。
2. 消元的每一步为z=1+y/2，x=1+y；代入4y=4+x+2z，得到4y=4+1+y+2+y=7+2y，所以y=3.5、z=2.75、x=4.5。靠近边界的状态期望更小，也给出合理性检验。

易错点与面试表达

“到边界”要明确是进入边界格就停；若把边界外一格才算停止，状态和答案都会改变。

第9题：每个新数都是当前最大或最小

完整题面：将1,2,…,8随机排列，要求每个数都大于它前面的所有数，或者小于它前面的所有数，满足条件的概率是多少？

答案：1/315。

概念补课：前缀最大值是从左读到当前位置时见过的最大数，前缀最小值同理。倒着删除更容易：最后一个数只能是全局最大或全局最小。

先识别模型

每个新数都是前缀最大或最小，等价于每次加入一个新的左右端点记录。

逐步推导

1. 从后往前看，最后一个数必须是全局最大值或全局最小值。
2. 删掉最后一个数后，剩余排列仍满足同样条件。
3. 因此有效排列数满足aₙ=2aₙ₋₁，a₁=1，得到a₈=2⁷。
4. 总排列数为8!，概率为2⁷/8!=1/315。

推导补全：把关键一步展开

1. 递推依赖双向映射：合格n排列删去末位后仍合格，末位一定是剩余范围两端之一；反过来，任意合格n−1排列补上一个新的全局最小或最大都合格。两类互斥，才可以写aₙ=2aₙ₋₁。
2. 用前缀相对排名也可算：第k个数在前k个中的排名均匀，为最小或最大概率2/k；随机排列的逐步插入排名独立，因此乘积∏(2/k)=2ⁿ⁻¹/n!，与倒删法一致。

易错点与面试表达

不要把“比前一个大/小”误读成局部相邻比较；题面是比前面所有数都大或都小。

第10题：均匀取数直到累计和超过1

完整题面：每次独立地从[0,1]均匀随机取一个数，累计和第一次大于1时停止，求停止时累计和的期望。

答案：\(e/2\approx 1.359\)。

概念补课：把第i次抽到的数记为\(X_{i}\)，抽取次数记为\(N\)，停止时的总和就是\(X_{1}+\cdots +X_N\)。解题分两步：先算平均抽几次\(E[N]\)，再算这些抽样加起来的平均值。均匀分布在[0,1]上的单次数平均为1/2。

先识别模型

累计和每次增加一个独立的[0,1]随机数，第一次超过1就停止。记\(S_{k}=X_{1}+\cdots +X_{k}\)，那么\(N\)是第一个满足\(S_{n}>1\)的次数。求\(E[N]\)时，不直接数“第几次停”，而是先求每个k下“抽完k次还没停”的概率。

先从二维三角形看概率

看前两次抽样，把\((X_{1},X_{2})\)当作正方形中的一个点。每个坐标都在0到1之间；由于两次抽样独立且均匀，所有可能组合在单位正方形里均匀铺开，正方形面积是1。条件\(X_{1}+X_{2}\le 1\)把正方形沿对角线切开，符合条件的部分是半个正方形，合格区域面积除以总面积1，概率为\(1/2\)。

三维：固定一个数，再算剩下的三角形

现在看\(X_{1}+X_{2}+X_{3}\le 1\)。固定第一次抽到\(X_{1}=x\)，剩下两数必须满足\(X_{2}+X_{3}\le 1-x\)。注意\(X_{2}\)和\(X_{3}\)仍各自可以取0到1之间的数；所有可能组合仍均匀铺在面积为1的单位正方形里。符合条件的点落在直线\(X_{2}+X_{3}=1-x\)下方，是一个直角三角形。三角形的两条直角边长都是\(1-x\)，因此它在单位正方形中所占的概率为\((1-x)^{2}/2\)。

例如\(x=0.4\)时，剩余额度是0.6。合格的组合是顶点为\((0,0)\)、\((0,0.6)\)、\((0.6,0)\)的三角形，面积为\(0.6\times 0.6/2=0.18\)。边长0.6的正方形只是包住这个三角形、帮助算面积；真正的抽样范围仍是整个单位正方形。

第一次抽到的\(x\)会在0到1之间变化。对每个可能的\(x\)，上面的三角形面积不同；当第一次抽样落在一个很窄的区间\([x,x+dx]\)时，它发生的概率约为\(dx\)；这小段对总概率的贡献就是“三角形面积×dx”。把\(x\)从0到1的所有小段加起来，就是下面这个积分：

\(P(X_{1}+X_{2}+X_{3}\le 1)=\int _{0}^{1}(1-x)^{2}/2 dx\)

把平方展开：\((1-x)^{2}/2=1/2-x+x^{2}/2\)。逐项积分得到\(1/2-1/2+1/6=1/6\)。所以三次抽完还没有超过1的概率是\(1/6=1/3!\)。

推广到更高维：每次固定一个坐标

高维不需要真的画出来，继续做同一件事：固定一个数，剩下的是低一维、额度更小的同类区域。记\(V_{m}(t)\)为m个相互独立、各自在[0,1]均匀抽取的数满足“总和不超过t”的概率；本题中\(0\le t\le 1\)，联合概率密度为1，因此这个概率就等于对应区域的m维体积。

1. 一个数时，符合\(X_{1}\le t\)的区间长度是\(t\)，故\(V_{1}(t)=t=t/1!\)。
2. 假设剩下m−1个数、额度为u时，概率是\(V_{m-1}(u)=u^{m-1}/(m-1)!\)。固定第一个数为\(x\)，剩余额度就是\(t-x\)；把\(x\)从0加到t，得到\(V_{m}(t)=\int _{0}^{t}(t-x)^{m-1}/(m-1)! dx\)。
3. 这个积分等于\(t^m/[m(m-1)!]=t^m/m!\)。也就是说，每增加一维，积分会再除以一个m，分母便从\((m-1)!\)变成\(m!\)。

例如四次抽样时，固定\(X_{1}=x\)后，剩下三数的合格区域体积为\((1-x)^3/3!=(1-x)^{3}/6\)；再从0积到1，得到\(1/24=1/4!\)。一般地，\(P(S_{k}\le 1)=1/k!\)。

积分可以用最基本的幂次公式来算：\(\int _{0}^{t}(t-x)^{m-1}dx=t^m/m\)，因为\(-(t-x)^m/m\)求导后正好是\((t-x)^{m-1}\)。因此上一行乘上\(1/(m-1)!\)后就是\(t^m/m!\)。

用尾和公式求平均抽取次数

如果最后抽了3次，那么\(N>0\)、\(N>1\)、\(N>2\)都成立，后面的条件都不成立。因此整数\(N\)可以写成\(\mathbf1_{\{N>0\}}+\mathbf1_{\{N>1\}}+\mathbf1_{\{N>2\}}+\cdots\)，两边取平均就得到尾和公式：\(\mathbb E[N]=\sum_{k\ge0}P(N>k)\)。这里每个\(\mathbf1_{\{\text{条件}\}}\)在条件成立时为1，否则为0。

\(N>k\)表示抽完前k次还没停，也就是\(S_{k}\le 1\)，概率为\(1/k!\)。所以\(\mathbb E[N]=\sum_{k\ge0}\frac1{k!}=1+1+1/2!+1/3!+\cdots=e\approx2.718\)。

用 Wald 恒等式求停止时的总和

每个\(X_{i}\)的平均值为\(1/2\)。虽然抽取次数\(N\)由抽样过程决定，但是否需要抽第i次，只取决于前i−1次的和；它不可能知道第i次将抽到什么。因此第i次抽样的平均贡献是\((1/2)P(N\ge i)\)。

把所有可能抽到的次数加起来：\(\mathbb E[\text{停止时累计和}]=\frac12\sum_{i\ge1}P(N\ge i)=\frac12\mathbb E[N]=e/2\approx1.359\)。这里的概率和\(\sum_{i\ge1}P(N\ge i)\)只是把尾和公式的下标整体前移一格，所以等于\(E[N]\)。这就是本题里的Wald恒等式；它适用于这里，是因为每次抽样彼此独立、分布相同，而且是否抽下一次由此前的结果决定。

推导补全：把关键一步展开

1. 尾和公式从\(N=\sum_{k\ge0}\mathbf1_{\{N>k\}}\)得到。这里\(P(N>k)=P(S_k\le1)=1/k!\)，其中k=0也贡献1；故\(\mathbb E[N]=\sum_{k\ge0}1/k!=e\)，不应从k=1开始而漏掉第一次抽样。
2. Wald等式可以不当黑箱：\(\mathbb E[\sum_{i=1}^N X_i]=\sum_{i\ge1}\mathbb E[X_i\mathbf1_{\{N\ge i\}}]\)。事件N≥i只由前i−1次抽样决定，与Xᵢ独立，因此每项为(1/2)P(N≥i)，总和为E[N]/2=e/2。

易错点与面试表达

固定\(X_{1}=x\)后，\(X_{2},X_{3}\)的可能取值仍在整个单位正方形里；随\(x\)缩小的是满足总和条件的三角形。尾和公式先给出平均抽取次数\(e\)，不是停止时总和；还要再乘每次抽样的均值\(1/2\)。停止时总和必然大于1，而其平均值\(e/2\approx 1.359\)也因此大于1。

第11题：红球先抽完时剩余蓝球

完整题面：袋中有m个红球和n个蓝球，不放回随机抽取；如果红球先被抽完，求此时平均还剩几个蓝球？

答案：(m+n)/(m+1)。

概念补课：条件期望是只在条件成立的样本中取平均。令K为最后一个红球后的蓝球数，则K>0恰好等价于“红球先抽完”。

先识别模型

这是条件顺序统计。先算末尾蓝球串长度的无条件期望，再除以“红球先耗尽”的概率。

逐步推导

1. 把所有球随机排列，K表示最后一个红球之后连续蓝球的数量。
2. 任意指定蓝球排在全部m个红球之后的概率是1/(m+1)，所以E[K]=n/(m+1)。
3. 红球先抽完等价于最后一球是蓝球，概率为n/(m+n)。
4. 在“红球没有先抽完”的样本里K=0，所以\(E[K]=P(\text{红先完})\times E[K\mid \text{红先完}]\)。移项得到\(E[K\mid \text{红先完}]=(n/(m+1))/(n/(m+n))=(m+n)/(m+1)\)。

推导补全：把关键一步展开

1. 令每个蓝球的指标为它是否位于所有红球之后。只看该蓝球与m个红球的相对顺序，它最后出现的概率为1/(m+1)，其他蓝球的位置可以忽略，所以n个指标的期望相加为n/(m+1)。
2. 条件事件A等价于最后一球为蓝球，且A不成立时K=0。全期望E[K]=E[K|A]P(A)+0给出除法。需假设m,n均为正；n=0时P(A)=0，条件期望无定义。

易错点与面试表达

直接报n/(m+1)漏掉了条件，只得到无条件尾部长度。

第12题：73人的相同生日配对

完整题面：在某年365天出生的人中随机抽取73人，平均有几对人的生日相同？

答案：7.2。

概念补课：指标变量只取0或1：事件发生记1，否则记0。它的期望等于事件概率；期望相加不要求各事件独立。

先识别模型

题目问相同生日“配对数”的期望，不是至少出现一对的概率。

逐步推导

1. 对每一对人定义指标Iᵢⱼ，生日相同则为1，否则为0。
2. E[Iᵢⱼ]=1/365。
3. 共有\(\binom{73}{2}=73\times 72/2=2628\)对，线性相加得到\(2628/365=7.2\)。

推导补全：把关键一步展开

1. 2628/365恰好等于7.2，因为365×7.2=2628。三个人同生日会贡献三对，而不是只算一个事件；这个计数单位是本题与生日碰撞概率的关键区别。
2. 如果各天生日概率为p₁,…,p₃₆₅，两人同生日概率改为\(\sum_{d=1}^{365}p_d^2\)，配对期望改为C(73,2)\(\sum_{d=1}^{365}p_d^2\)。由平方和下界\(\sum_{d=1}^{365}p_d^2\)≥1/365，均匀生日模型实际上使碰撞配对期望最小。

易错点与面试表达

配对事件之间不独立没关系；只有问“至少一对”时才需要容斥。

第13题：到达3前访问−2的次数

完整题面：从0开始的随机游走每次等可能加1或减1，求首次到达3之前访问−2的次数的期望。

答案：6。

概念补课：令τ₃为第一次到达3的时刻，V表示τ₃之前走到−2的总次数，第一次抵达−2也算一次。题目可以拆成“先到过−2的概率”乘“到过后平均访问几次”。区间随机游走的边界命中概率是线性的；每次离开−2后，未来用新的独立步长继续，所以回返会重复。

先识别模型

从0出发，不一定能先到−2：有些路径先到3，访问次数为0。即使先到了−2，也可能离开后反复回来。先算“第一次到−2”的概率，再算“到−2之后总访问次数”的条件期望，最后相乘。

逐步推导

1. 先解释赌徒破产公式。设游走在整数边界\(L\)和\(R\)之间，当前位置是\(x\)。令\(u(x)\)为先到\(R\)的概率，则边界上\(u(L)=0,u(R)=1\)；从中间一步等可能左右走，故\(u(x)=[u(x-1)+u(x+1)]/2\)。这说明相邻位置的概率差相同，\(u(x)\)沿位置线性变化，所以\(u(x)=(x-L)/(R-L)\)；先到左边界的概率就是\(1-u(x)=(R-x)/(R-L)\)。
2. 把\(L=-2,R=3,x=0\)代入，先到3的概率是\(2/5\)，先到−2的概率是\(1-2/5=3/5\)。记这个“先到−2”的事件为A。
3. 现在假设已经在−2，当前这一次先计入访问次数。下一步有一半概率走到−3：从−3最终回到−2的概率为1，因为一维公平随机游走会以概率1返回任意固定邻点。也可把游走限制在\([-M,-2]\)里看，先到−2的概率是\((M-3)/(M-2)\)；令\(M\)不断增大，这个概率趋近1。
4. 另一半概率走到−1。从−1出发，先到−2而不是3的概率是\((3-(-1))/(3-(-2))=4/5\)。因此离开−2后再回到−2的总概率为\(q=(1/2)\times 1+(1/2)\times (4/5)=9/10\)。
5. 设已经访问过−2之后，包含当前这一次在内的未来总访问次数期望为\(G\)。当前这次贡献1；以概率\(q=9/10\)回来后，又回到同一个问题，贡献期望\(G\)。所以\(G=1+(9/10)G\)，解得\(G=10\)。等价地，访问次数的期望是\(1+q+q^{2}+\ldots =1/(1-q)=10\)；这里的1已经包含第一次访问。
6. 若事件A不发生，访问次数为0；若A发生，后续平均访问10次。总期望因此是\(E[V]=P(A)\times E[V\mid A]=(3/5)\times 10=6\)。

推导补全：把关键一步展开

1. 一般地，从0到正整数b之前访问负整数−a的期望为2b：先到−a概率b/(a+b)；到达后每次离开不再返回的概率是(1/2)×1/(a+b)，所以含当前访问的次数均值是2(a+b)。相乘后a消去。
2. 有限访问期望不代表有限停止时间期望。半直线上公平游走虽几乎必然最终到3，但E[τ₃]为无穷；本题数的是某个固定位置的访问次数，不能对τ₃直接套一个未经验证的可选停止公式。

易错点与面试表达

\(3/5\)只是“至少访问一次”的概率，\(10\)是“已到达−2后，包含首次在内的平均总访问次数”；两者相乘才是从0出发的无条件期望。若把10理解成“额外返回次数”，会多算或少算1次。

第14题：三根不均匀绳子测7分钟

完整题面：三条不均匀绳子，每条恰好燃烧8分钟，如何用它们计时7分钟？

答案：7分钟。

概念补课：不均匀表示烧掉一半长度未必用一半时间；但从剩余绳段两端同时烧，两个火头共同消耗它，剩余燃烧时间一定减半。

先识别模型

不均匀绳子不能靠长度计时，但从两端同时燃烧一定把剩余燃烧时间减半。

逐步推导

1. 时刻0：第一根两端点燃，第二、三根各点一端。
2. 第4分钟第一根烧完；点燃第二根另一端。
3. 第二根此前还剩4分钟单端时间，改两端后2分钟烧完，即第6分钟。
4. 第三根已单端烧过6分钟，只剩2分钟单端时间；第6分钟点另一端，再过1分钟烧完。

推导补全：把关键一步展开

1. 每个时间点要由“某根绳烧完”触发，而不能假装已有钟表知道4、6分钟。第一根烧完触发第二根补火头，第二根烧完再触发第三根补火头，三个触发事件分别出现在4、6、7分钟。
2. 两端减半基于同一段绳子的单端燃烧时间可加，且燃烧速度只由绳段决定、两端互不干扰。若现实材料从不同方向燃烧速度不同，该理想化计时方法的前提就失效。

易错点与面试表达

不能假定绳子长度均匀；可靠的是“整根单端8分钟”和“剩余部分两端减半”。

第15题：圆心在自交四边形内部

完整题面：圆周上顺时针随机取4个点，依次记为A、B、C、D，求圆心位于自交四边形ACBD内部的概率。

答案：1/4。

概念补课：四点的凸包是包住它们的最小凸多边形。圆心不在四点凸包内，当且仅当四点可被某个半圆覆盖；自交四边形的“内部”还需明确采用哪种定义。

先识别模型

自交四边形的“内部”容易引起歧义。先判断圆心是否在四点凸包内，再利用对称性判断它落在哪个三角形。

逐步推导

1. 四个圆周点全落在某个半圆内的概率是1/2，因此圆心在普通凸四边形内的概率是1/2。
2. 两条对角线把凸四边形分成四个三角形。
3. 自交路径ACBD对应其中相对的两块；在凸包事件内，圆心落入这两块的概率由标签对称性为1/2。
4. 总概率为1/2×1/2=1/4。

推导补全：把关键一步展开

1. 半圆覆盖概率的来源：以每个采样点为半圆起点，其余三点都位于顺时针半圆的概率为(1/2)³；除零概率的边界情形，这四类事件互斥，故覆盖概率4/8=1/2。
2. 另一个1/2来自循环标签对称，而不是声称四块三角形面积相同。固定不含圆心在对角线上的配置，循环平移A、B、C、D的起点标签会交替选中两组相对区域；随机标签下选中的概率为1/2。

易错点与面试表达

若采用不同的自交多边形“内部”定义，必须先说明采用偶奇规则还是绕数规则；原题默认的是两瓣区域。

第16题：9枚对10枚硬币是否公平

完整题面：A、B分别投9枚、10枚硬币；如果B的正面数严格多于A则B赢，否则A赢。这个游戏公平吗？

答案：公平。

概念补课：两个同分布的随机变量交换名字后样本空间不变，所以两组都投9枚时，A领先与B领先概率相同；多出的第10枚只需分析它能否改变胜负。

先识别模型

最后一枚硬币只在前9枚平局时有作用。把样本按前9枚的胜负分成三类即可。

逐步推导

1. P(B前9多)=P(A前9多)，因为两组9枚硬币同分布。
2. B前9少时，第10枚正面最多追平，仍由A赢。
3. 前9枚平局时，第10枚正面B赢、反面A赢，各占一半。
4. 所以两方总胜率相同，游戏公平。

推导补全：把关键一步展开

1. 记前9枚差值D=B₉−A₉，平局概率为t。对称性给P(D>0)=P(D<0)=(1−t)/2；多的一枚只有在D=0时改变胜负，故P(B赢)=(1−t)/2+t/2=1/2。
2. 独立公平硬币是充分前提。若额外一枚正面概率为p而前9枚仍同分布，B胜率变为(1−t)/2+pt=1/2+(p−1/2)t；可以精确看出公平性依赖在哪里。

易错点与面试表达

若规则改成“平局算和局”或“B多或相等都赢”，结论会变；这里是严格多于。

第17题：绳子对折n次后从中间剪

完整题面：一根绳子对折n次，从中间剪开，展开后有几段？

答案：2ⁿ+1段。

概念补课：切点与绳段不同：一根绳上0个切点是1段，k个互异内部切点是k+1段。每对折一次，重叠层数翻倍。

先识别模型

折叠把一刀复制到多个层，展开后数的是不同切点，段数再比切点多1。

逐步推导

1. 对折n次后有2ⁿ层。
2. 从中间剪开，相当于在原绳上产生2ⁿ个内部切点。
3. k个互异内部切点把一根连通绳子分成k+1段。
4. 答案为2ⁿ+1。

推导补全：把关键一步展开

1. 以原绳归一化为[0,1]，反复标准对折n次后在叠层中点剪开，展开的切点为(2j−1)/2ⁿ⁺¹，j=1,…,2ⁿ。这些点互异且都在内部，所以确实是2ⁿ个切点。
2. n=0时没有对折但中间剪一刀，应为2段；n=1时切点1/4、3/4得到3段。用这两个最小例子可迅速排除把层数2ⁿ直接当段数的错误。

易错点与面试表达

若刀口正好落在折痕，多个切点可能重合；题目默认普通中间位置。

第18题：随机子集形成链

完整题面：在{1,2,3,4,5}的子集中有放回地随机取3个集合A、B、C，求A⊆B⊆C的概率。

答案：1/32。

概念补课：随机选一个子集，等价于让每个底层元素独立抛一次公平硬币决定是否放入。于是一个元素在A、B、C中的归属可写成三位0/1串。

先识别模型

把集合包含关系逐元素拆开，五元素问题变成五个独立的三比特状态问题。

逐步推导

1. 一个元素在A、B、C中的状态共有8种。
2. A⊆B⊆C只允许000、001、011、111四种单调状态。
3. 单个元素满足条件的概率是4/8=1/2。
4. 五个元素独立，概率为(1/2)⁵=1/32。

推导补全：把关键一步展开

1. 全部三元集合共有(2⁵)³=2¹⁵种。每个底层元素只能选择四种单调归属，五个元素合计4⁵=2¹⁰种；分子分母相除再得2⁻⁵。两种计数方式也验证了逐元素独立的使用。
2. 若改成k个集合构成弱包含链，一个元素的k位归属只能先0后1，共k+1种；m个底层元素时概率[(k+1)/2ᵏ]ᵐ。若要求严格包含，每一步都必须至少新增一个元素，不能继续直接用该式。

易错点与面试表达

A、B、C是随机子集，不是从集合里抽出的三个元素；这是本题最常见的读题错误。

第19题：只有“至少一位正确”的三位密码锁

完整题面：三位数字密码锁每次尝试后只能知道是否至少有一个数字与位置都正确，至少尝试多少次才能保证找到密码？

答案：最坏情况13次，而且12次不可能。

概念补课：一次只返回“是/否”不代表必然提供完整1比特有效信息；若反馈把候选集切成1和999两块就很不均衡。最坏情况分析必须照顾每个分支。

先识别模型

这是带“是否至少一位位置正确”反馈的自适应识别问题。先识别每个位置还允许哪些数字，再识别最终排列。

逐步推导

1. 依次试000、111、……、999。试ddd时，“是”表示至少一个位置的密码数字为d；这10次会把候选空间压缩成由三位所用数字及其位置关系决定的小集合。
2. 若最终涉及三个不同数字a、b、c，取未出现数字d，试abd、dab、bda；三条真假反馈可区分六种排列。
3. 若只涉及两个不同数字a、b，取未出现数字d，用add、dad、dda分别探测每个位置是否为a。三个真假反馈直接给出a的位置，其余位置必为b，可区分全部六种密码；全相同密码在第一阶段结束后即可确定。
4. 为什么不能12次：连续6次全否定后，每个位置至少还有4个候选，共64个状态；剩余6次反馈若要完成识别，下一次必须把64精确分成32/32，但一次询问只能产生16、28或37个“是”状态。

推导补全：把关键一步展开

1. 把下界里“至少4个候选”展开：沿前六次全部否的分支，每个位置至多排除6个数字，可各选4个尚未排除数字形成4³=64个子候选。第7问只可能在其中0、1、2、3个位置使用候选数字，“是”分支大小为0、16、28、37之一，均非32；另一个分支就超过32，余下5个真假反馈最多区分32种，因此12问不够。
2. 上界中的三不同数字可实际列码验证：对六种排列abc、acb、bac、bca、cab、cba，询问abd、dab、bda分别产生100、110、011、001、010、101，六码互异。这里“找到”指确定完整密码；若额外要求在最后一次实际开锁，需把确认后的输入动作单独计数。

易错点与面试表达

这里默认密码允许数字重复和前导零，反馈是“至少一位数字与位置同时正确”。若反馈语义改变，候选状态和策略都必须重建。

第20题：抽到比上一个数大的数就停

完整题面：每次均匀随机取[0,1]中的一个数；如果它大于上一个数就停止，求最后一个数的期望。

答案：2−e/2≈0.64086。

概念补课：递推函数\(f(x)\)把历史压缩成“上一数是x”。积分\(\int _{0}^{x}f(u)du\)表示下一数落在0到x后，对所有后续期望按密度1加权。

先识别模型

当前状态只有“上一个数x”，所以可以写一维递推函数，而无需记住全部历史。

逐步推导

1. 定义f(x)：已看到上一数x后，最终停止数的期望。
2. 下一次u≤x则继续，贡献f(u)；u>x则停止，贡献u。
3. 所以\(f(x)=\int _{0}^{x}f(u)du+\int _{x}^{1}u du\)。两边对x求导：第一项导数是f(x)，第二项导数是−x，于是\(f'(x)=f(x)-x\)。
4. 当x=0，下一数几乎必然大于0并立即停止，所以\(f(0)=E[U]=1/2\)。解一阶方程得\(f(x)=1+x-e^{x}/2\)。
5. 第一次数X₁也均匀，因此总期望为\(\int _{0}^{1}f(x)dx=3/2-(e-1)/2=2-e/2\)。

推导补全：把关键一步展开

1. 微分方程的解法是乘积分因子e⁻ˣ：d[e⁻ˣf(x)]/dx=−xe⁻ˣ。积分并代f(0)=1/2，得到e⁻ˣf(x)=(x+1)e⁻ˣ−1/2，即f(x)=1+x−eˣ/2。
2. 这里初始还没有“上一数”，所以必须对第一次X₁再平均：\(\int_0^1 f(x)\,dx=2-e/2\)。它与第37题结果相同，但第10题的累计总和期望是e/2，二者数值不同。

易错点与面试表达

第10题求最终累计和，期望e/2；本题求遇到相邻上升时的最后一个数，期望2−e/2。两者不相同，不要混淆。

第21题：随机±1矩阵行列式的方差

完整题面：A是n×n矩阵，矩阵元素独立地随机取+1或−1，求det(A)的方差。

答案：n!。

概念补课：方差公式是\(\operatorname{Var}(D)=E[D^{2}]-E[D]^{2}\)。行列式展开有n!项；独立对称±1变量均值为0，乘积中只要某变量只出现一次，整项期望就是0。

先识别模型

随机±1矩阵题用行列式排列展开，核心是独立均值为0的变量会让交叉项消失。

逐步推导

1. \(\det(A)=\sum_{\sigma}\operatorname{sgn}(\sigma)\prod_{i=1}^n a_{i,\sigma(i)}\)，均值为0。
2. 平方后出现排列σ、τ的交叉项。
3. 若σ≠τ，至少有一个矩阵元素只出现一次，期望为0。
4. 只有σ=τ时每个元素都平方为1，共n!项，因此方差为n!。

推导补全：把关键一步展开

1. 若σ≠τ，取某一行i使σ(i)≠τ(i)。变量aᵢ,σ(i)在两个排列乘积里只出现一次，而且不可能在其他行重复出现；先对它取期望就是0，整项归零。这样才严格解释了交叉项消失。
2. 更一般地，若所有元素独立、均值0、方差σ²，行列式平方中每个同排列项期望为(σ²)ⁿ，故Var(det A)=n!σ²ⁿ。只靠“每个元素对称”而没有独立性，并不足以得到这个结论。

易错点与面试表达

若元素不独立、不是对称±1，交叉项未必全消失，不能照搬n!。

第22题：最大值加最小值大于1

完整题面：在[0,1]上均匀随机取n个数，求最大值与最小值之和大于1的概率。

答案：1/2。

概念补课：分布对称法是在样本间建立一一配对。把每个样本Xi换成1−Xi仍然同样可能，却会把“最大加最小大于1”和“小于1”互换。

先识别模型

利用Xi→1−Xi的分布对称性，不需要求最大值和最小值的联合密度。

逐步推导

1. 令M=maxXi、m=minXi。
2. 变换后最大值和最小值之和变成2−(M+m)。
3. 原分布与变换后相同，所以P(M+m>1)=P(M+m<1)。
4. 连续分布下等号概率为0，故答案1/2。

推导补全：把关键一步展开

1. 映射T(x₁,…,xₙ)=(1−x₁,…,1−xₙ)是自身的逆，既保留样本概率，又把和S=M+m变成2−S。两侧事件因此等概率，再用P(S=1)=0才能把概率定为1/2。
2. 对离散对称分布仍有P(S>1)=P(S<1)，但两者等于[1−P(S=1)]/2。以只取0、1的样本为例，等号可能占大部分概率，说明连续性不是装饰条件。

易错点与面试表达

离散分布会有M+m=1的正概率，此时不能直接说两边各一半。

第23题：十局后有3元且中途未破产

完整题面：有1元的赌徒，每局以相同概率赢1元或输1元。已知10局后有3元，求他中途没有破产的概率。

答案：3/7。

概念补课：给定终点已经筛掉大部分路径，分母只能数符合终点的路径。反射原理把曾碰到0的坏路径，把第一次碰到0之前的前缀翻转，变成从−1出发的普通路径。

先识别模型

这是给定终点的随机游走路径计数，反射原理负责删除“曾经破产”的坏路径。

逐步推导

1. 从1到3的净增量是2，十局中必须6胜4负，共C(10,4)=210条路径。
2. 曾经到过0的路径，在第一次到0处反射，和从−1到3的路径一一对应。
3. 从−1到3需7胜3负，坏路径数C(10,3)=120。
4. 安全路径90条，条件概率90/210=3/7。

推导补全：把关键一步展开

1. 反射时应反射第一次碰到0之前的整段前缀：起点1变为−1，碰零位置仍是0，之后通往终点3的后缀不动。若反射后缀，得到的是终点变号的另一种计数法，不能同时说起点改成−1。
2. 一般从a>0出发，N步到b>0，若奇偶可达，坏路径数为C(N,(N+b+a)/2)，总数为C(N,(N+b−a)/2)。代a=1、b=3、N=10，分别为C(10,7)=120与C(10,6)=210。

易错点与面试表达

分母是“十局后有3元”的条件路径数，不是全部2¹⁰条路径；若问联合概率，答案会是90/2¹⁰。

第24题：最多掷3次公平骰子的最优停止价格

完整题面：最多投3次公平骰子，可以随时停止并以最后一次点数为收益，求这个游戏的公平价格（最优期望收益）。

答案：14/3。

概念补课：公平价格是按最优策略玩时的期望收益。若未来继续的价值为c，当前见到点数x就取\(\max(x,c)\)：x高于c便停，否则继续。

先识别模型

有限次数最优停止必须倒推，每一层都比较“现在拿”与“继续的期望”。

逐步推导

1. 最后一次只能接受点数，价值3.5。
2. 还剩两次时，1、2、3小于3.5，重掷；4、5、6停止，价值\((3\times 3.5+4+5+6)/6=17/4\)。
3. 还剩三次时，1到4小于继续价值17/4，故重掷；5、6停止，价值\((4\times 17/4+5+6)/6=14/3\)。

推导补全：把关键一步展开

1. 设 \(V_k\)为尚有k次可掷、还没有看到下一点数时的最优价值，则V₁=3.5，\(V_k=\frac16\sum_{x=1}^6\max(x,V_{k-1})\)。当前已掷出x时，比较的是\(x\) 和 \(V_{k-1}\)，不要把“还可掷几次”与“已经掷几次”混在一起。
2. V₂=4.25介于4与5，故三次版本的首轮停止集合为{5,6}；若继续到第二轮，阈值重新变为3.5，停止集合为{4,5,6}。同一道题不同轮次的阈值并不相同。

易错点与面试表达

不能把三次骰子的均值简单相加；允许停止意味着每一步都在做最大值比较。

第25题：布朗运动退出±1区间的条件时间

完整题面：Wₜ是一维标准布朗运动，τ=inf{t:Wₜ=1或Wₜ=−1}，求E[τ | Wτ=1]。

答案：1。

概念补课：停止时间τ是路径第一次碰到+1或−1的时刻。对称性把“向上退出且耗时t”的路径与“向下退出且耗时t”的路径配对，所以两种条件耗时分布相同。

先识别模型

布朗运动退出区间的时间与向上/向下出口在对称性下同分布，也可以用边值问题直接算。

逐步推导

1. 从0出发到+1和−1的概率各为1/2。
2. 反射x→−x把向上出口路径映到向下出口路径，同时保持退出时间。
3. 因此条件退出时间期望等于无条件Eτ。
4. 鞅Wₜ²−t在τ处给出Eτ=E[Wτ²]=1。

推导补全：把关键一步展开

1. 为合法使用停止公式，先截断\(\tau_n=\min(\tau,n)\)。由于停止前|W|≤1，\(\mathbb E[\tau_n]=\mathbb E[W_{\tau_n}^2]\le1\)；单调收敛得E[τ]≤1，故τ几乎必然有限。再由路径连续与有界收敛得\(\mathbb E[W_\tau^2]=1\)，因此E[τ]=1。
2. 对称性给的是\(P(\tau\in B,W_\tau=1)=P(\tau\in B,W_\tau=-1)\)，对任意时间集合B均成立；由此两种条件时间分布相同，而不只是两个出口概率各1/2。

易错点与面试表达

若起点不是0或边界不是对称的±1，条件退出时间一般不再相同。

第26题：三个变量相关系数下界

完整题面：X、Y、Z三个随机变量两两相关系数均为ρ，求ρ的最小值。

答案：−1/2。

概念补课：相关矩阵必须半正定，通俗说任何线性组合的方差不能为负。标准化后\(\operatorname{Var}(X+Y+Z)=3+6\rho \)，因此ρ至少为−1/2。

先识别模型

三个相关系数能否同时存在，取决于相关矩阵是否半正定。

逐步推导

1. 标准化后，\(\operatorname{Var}(X+Y+Z)=3+2(\rho +\rho +\rho )=3+6\rho \ge 0\)，故\(\rho \ge -1/2\)。
2. 相关矩阵的特征值是\(1-\rho ,1-\rho ,1+2\rho \)，非负条件给出完整范围\(-1/2\le \rho \le 1\)。
3. 取独立标准正态U、V，令\(X=U\)、\(Y=-U/2+\sqrt{3}V/2\)、\(Z=-U/2-\sqrt{3}V/2\)，三组相关系数全为−1/2，说明下界可达。

推导补全：把关键一步展开

1. 先把原变量减均值、除标准差，要求各方差有限且大于0，相关系数才定义良好。协方差项共有三对，每对在Var(X+Y+Z)中出现两次，因此系数是6ρ而非3ρ。
2. 构造达到下界时可直接检查Cov(X,Y)=−1/2、Cov(X,Z)=−1/2，Cov(Y,Z)=1/4−3/4=−1/2，且三者方差均为1。此时X+Y+Z恒为0，对应相关矩阵的一个零特征值。

易错点与面试表达

只给特征值下界还不完整；最好同时给出达到下界的构造。

第27题：12枚硬币一枚异重

完整题面：12枚外观相同的硬币中只有1枚质量不同，用天平至少称几次才能保证找出这枚硬币？

答案：3次称重。

概念补课：天平一次有左重、平衡、右重三种结果，三次最多形成3³=27条路径。未知状态有12枚×偏重/偏轻=24种，所以两次肯定不够，三次才可能够。

先识别模型

12枚异重硬币是经典三结果信息编码问题。三次称重有27种结果，足以覆盖24种“硬币编号×轻重”状态。

逐步推导

1. 第一次把硬币分成4、4、4三组并称两组。
2. 平衡说明异常在未称组；不平衡则知道异常在盘上两组且轻重方向受约束。
3. 若第一次平衡，异常在9～12，且1号正常。第二次称9、10、11对1、2、3：平衡则12异常；不平衡则已知9～11中的异常偏重或偏轻，第三次称两个候选即可定位。
4. 若第一次左盘重，候选为1～4中某枚偏重，或5～8中某枚偏轻。第二次称\(1,2,5\)对\(3,6,9\)（9号正常）：左重留下“1重、2重、6轻”；右重留下“3重、5轻”；平衡留下“4重、7轻、8轻”。每组最多3个状态，第三次可区分；第一次右盘重时镜像处理。

推导补全：把关键一步展开

1. 第一次左重时，第二次左重分支{1重,2重,6轻}：称1对2即可区分；右重分支{3重,5轻}：称3对正常9，左重为3重，平衡为5轻；平衡分支{4重,7轻,8轻}：称7对8，平衡为4重，较轻盘上的硬币就是异常。
2. 第一次平衡后，若第二次9、10、11也平衡，已知12异常；若还要求辨别轻重，第三次12对正常1即可。若第二次不平衡，9～11中异常的轻重方向已知，第三次9对10可以区分三候选。

易错点与面试表达

信息容量27>24只是必要条件，不是策略本身；必须维护每个分支的候选状态。

第28题：n维单位球面两点弧长期望

完整题面：在n维单位球面上均匀随机取两个点，求两点之间较短大圆弧的期望长度。

答案：π/2。

概念补课：对跖点就是球面上正相反的点。单位球面一整条大圆周长2π，较短弧长L在[0,π]；把一点换成对跖点，弧长恰从L变为π−L。

先识别模型

球面弧长题只用到对跖反射对称，不需要知道高维球面的具体密度。

逐步推导

1. 记两点较短大圆弧长为L，单位球面上L∈[0,π]。
2. 把第二点反射到对跖点，弧长变为π−L，分布保持不变。
3. 所以E[L]=E[π−L]=π/2。

推导补全：把关键一步展开

1. 固定第一点u并利用旋转对称，令第二点为v；弧长L=arccos(u·v)。替换v→−v后，arccos(−u·v)=π−L。此处不需要L均匀，高维时其分布通常并不均匀。
2. E[L]=E[π−L]=π−E[L]，移项2E[L]=π。半径改为R时弧长全部乘R，答案为πR/2；环境须是存在大圆的正维球面，离散的零维两点球面不采用该路径定义。

易错点与面试表达

若问的是欧氏直线距离或指定非大圆路径，答案不是π/2；要先确认“弧长”的定义。

第29题：出现奇数前出现过所有偶数

完整题面：反复投掷公平骰子，求在第一次投出奇数之前已经投出过所有偶数面2、4、6的概率。

答案：1/20。

概念补课：骰子虽会重复很多次，题目只关心六个面谁第一次出现得更早。公平骰子的六个首次出现次序完全对称，可看成六个面的一次随机排列。

先识别模型

停止条件只依赖各面第一次出现的相对顺序，因此可以把无限投掷压成一次随机排列。

逐步推导

1. 六个面的首次出现顺序等可能，共6!种。
2. 在第一次奇数出现前见过2、4、6，等价于这三个偶数面占据首次出现顺序的前三位。
3. 前三位内部有3!种，后三个奇数内部有3!种。
4. 概率为3!×3!/6!=1/20。

推导补全：把关键一步展开

1. 首次出现顺序的对称性来自面标签可任意置换：任何指定先后次序都能由重命名映到其他次序，概率不变；六个面最终几乎必然全出现，所以6!类概率总和为1。
2. 也可忽略已见过的重复偶数：尚缺3、2、1个偶数时，下一个有意义的新面必须赢过3个奇数面，对应成功概率3/6、2/5、1/4；相乘为1/20。

易错点与面试表达

重复投掷次数不需要计算；只看第一次出现时间的排序即可。

第30题：100!的末位非零数字

完整题面：求100!的最后一位非零数字。

答案：4。

概念补课：末尾0来自因子10=2×5。阶乘里2远多于5，所以先配对并删去所有10，再算剩余乘积的个位；\(\bmod 10\)就是只保留除以10的余数。

先识别模型

末位非零数字由2和5配对产生的尾零控制。

逐步推导

1. 先统计100!中2和5的幂次，成对的2×5全部贡献尾零；2更多，去掉配对后仍有剩余。
2. 记D(n)为n!的最后非零位。按每5个连续整数分组可得递推\(D(n)=D(\lfloor n/5\rfloor )D(n \bmod 5)2^{\lfloor n/5\rfloor } \bmod 10\)，其中\(D(0..4)=1,1,2,6,4\)。
3. \(D(20)=D(4)D(0)2^{4}\equiv 4\)，再算\(D(100)=D(20)D(0)2^{20}\equiv 4\)，所以答案为4。

推导补全：把关键一步展开

1. 算术核查：2²⁰模10=6，因此D(100)=D(20)×6模10；D(20)=D(4)×2⁴模10=4×6模10=4，最后4×6模10=4。每步都保留末位，并未直接把100!取模。
2. 无须记递推也可写验证程序：逐个乘1到100，每乘一次删去所有尾零，再保留足够多的末尾数字；不过若只保留一位，遇到后续除10时可能丢失信息。证明解与数值验证的逻辑要分开。

易错点与面试表达

直接对100!取模10会得到0，必须先剥离尾零。

第31题：盒中球随机搬运直到集中

完整题面：n个盒子中每个盒子初始有1颗球；每次从位于不同盒子的球对中随机选一对，再随机选其中一颗放入另一颗所在的盒子，直到所有球集中到一个盒子，求平均操作次数。

答案：n(n−1)/2。

概念补课：势函数是给状态配一个“离终点还有多少”的分数。\(S=\sum_{i<j}x_i x_j\)数分处不同盒子的无序球对；全都集中时S恰为0。

先识别模型

这是一个用势函数求吸收时间的盒中球过程。势函数选成不同盒子之间的球对数，终止状态的势为0。

逐步推导

1. 设第i个盒有xᵢ个球，定义S为所有i小于j的xᵢxⱼ之和。
2. 初始每盒1球，S₀=C(n,2)；所有球集中后S=0。
3. 若一对跨盒球分别来自含a、b颗球的盒子，两种搬运方向使势分别变化\(a-1-b\)和\(b-1-a\)，平均恰好为−1。
4. 所以Sₜ+t是鞅，停止时E[T]=S₀=n(n−1)/2。

推导补全：把关键一步展开

1. 用\(S=[n^2-\sum_i x_i^2]/2\)重算漂移：从a盒移1球到b盒时，平方和变化(a−1)²+(b+1)²−a²−b²=2(b−a+1)，故ΔS=a−b−1；反方向为b−a−1，两者平均−1。
2. 停止时间也可先截断。S始终非负且有界，\(\mathbb E[S_{T\wedge m}]+\mathbb E[T\wedge m]=S_0\)，先得到E[T]≤S₀与几乎必然吸收，再用有界收敛\(\mathbb E[S_{T\wedge m}]\to0\)，才合法得E[T]=S₀。

易错点与面试表达

如果把题面误读成“随机选有球盒，再均匀选目标盒”，转移概率与答案都会改变；必须先澄清抽样单位是跨盒球对。

第32题：三个六面骰子和一个二十面骰子谁大

完整题面：分别投掷三个六面骰子并把点数相加，再投一个20面骰子比较大小。这个游戏公平吗？

答案：公平。

概念补课：公平不要求两边点数分布相同，只要求交换胜负后概率相同。三个六面骰子逐个用d→7−d反射，总和X变为21−X；二十面骰子也能用y→21−y反射。

先识别模型

公平性用保持分布、交换胜负的反射映射证明，而不是比较两个骰子总期望。

逐步推导

1. 三骰和X的范围是3到18，二十面骰Y的范围是1到20。
2. 映射(X,Y)→(21−X,21−Y)保持联合分布。
3. 它把X>Y映成X<Y，因此双方胜率相等。
4. 平局概率为1/20，双方各胜19/40。

推导补全：把关键一步展开

1. 条件于X=x，Y在1～20均匀，所以P(X>Y|X=x)=(x−1)/20；平均后为(10.5−1)/20=19/40。相同方法得P(X<Y)=E[(20−X)/20]=19/40，并非由期望相等直接推出公平。
2. 平局概率为\(\sum_x P(X=x)P(Y=x)=\frac1{20}\sum_xP(X=x)=\frac1{20}\)，因为X所有可能值都在Y的取值范围内。三个概率19/40+19/40+1/20=1，完成检验。

易错点与面试表达

“公平”只表示胜率相同；不代表没有平局，也不代表两个随机变量期望相同。

第33题：圆内两点与圆心构成钝角三角形

完整题面：在圆内均匀随机取两个点，与圆心组成三角形，求这个三角形为钝角三角形的概率。

答案：3/4。

概念补课：三角形最多一个钝角，所以三处钝角事件可相加。圆内均匀取点的半径并不均匀：因面积随r²增长，有\(P(R\le r)=r^{2}\)，密度为2r。

先识别模型

三角形的钝角可能在圆心，也可能在两个随机点。必须把三种互斥事件都算上。

逐步推导

1. 较小圆心角θ在[0,π]均匀，所以θ>π/2的概率是1/2。
2. 若A、B半径为r、s，A处钝角等价于向量\(-A\)与\(B-A\)点积小于0，即\(r<s \cos \theta \)，这也要求θ<π/2。
3. 固定s、θ后，\(P(r<s \cos \theta )=s^{2}\cos ^{2}\theta \)。再平均s与θ：\(\mathbb E[s^2]=\int_0^1 s^2\cdot 2s\,ds=\frac12\)，而\(\mathbb E[\cos^2\theta\,\mathbf1_{\{\theta<\pi/2\}}]=\frac1\pi\int_0^{\pi/2}\cos^2\theta\,d\theta=\frac14\)，相乘得A处钝角概率1/8。B处同样为1/8。
4. 总概率1/2+1/8+1/8=3/4。

推导补全：把关键一步展开

1. 点A处角的点积是(−A)·(B−A)=r²−rs cosθ，严格小于0才是钝角，约去r>0得到r<s cosθ。先有cosθ>0才可能成立，所以积分只在θ∈[0,π/2]上。
2. 对给定s和θ，半径r的累积分布为r²，而不是r；因此条件概率为(s cosθ)²。再利用半径与角度独立，(1/2)×(1/4)=1/8。直角与共线是零概率事件，三种钝角事件互斥，才可直接相加。

易错点与面试表达

若两点是在圆周上而非圆内均匀抽取，半径不再随机，答案会改变；必须按原题区分。

第34题：2ⁿ的首位是1的频率

完整题面：求2ⁿ的十进制首位是1的长期频率（原题写作“概率”）。

答案：lg2≈0.3010。

概念补课：正数可写成\(10^{\text{整数部分}}\times10^{\text{小数部分}}\)，后一项决定首位。首位为1对应有效数字在[1,2)，取对数后小数部分落在\([0,\log_{10} 2)\)。

先识别模型

这是2的幂的首位数字问题，本质是无理数旋转的等分布。

逐步推导

1. 2ⁿ的首位为1等价于n·lg2的小数部分落在[0,lg2)。
2. lg2是无理数，序列n·lg2模1等分布。
3. 长期频率等于目标区间长度lg2≈0.3010。

推导补全：把关键一步展开

1. 若lg2=p/q为有理数，便有\(2^q=10^p=2^p5^p\)；素因子分解唯一性使其不可能，所以lg2确是无理数。无理数模1等分布定理给出区间频率等于长度，这一步是需要调用的定理，不能仅由“看起来随机”代替。
2. 首位d的一般目标是[lg d,lg(d+1))，频率lg(1+1/d)。九个首位频率相加为lg10−lg1=1，是概率总和的检查；n在小有限区间均匀取值时，频率只近似该极限。

易错点与面试表达

这里的“概率”应理解为n取很大范围时的自然密度，不是每个n独立随机。

第35题：掷骰子直到出现3，期间大于3的点数期望

完整题面：反复投掷公平骰子，直到第一次投出3；求在此之前投出的点数中大于3的次数的期望。

答案：3。

概念补课：几何分布描述第一次成功前有多少次失败。每次成功概率p时，失败次数期望是\((1-p)/p\)。本题把投出3视为成功，所以平均先有5次非3。

先识别模型

把“等到3要多久”和“期间出现哪类点数”拆开。

逐步推导

1. 出现3前的失败次数期望为(1−1/6)/(1/6)=5。
2. 给定一次失败，点数在1、2、4、5、6中均匀。
3. 其中大于3的有4、5、6三个，占3/5。
4. 期望次数为5×3/5=3。

推导补全：把关键一步展开

1. 直接首步递推可避免条件样本量的疑虑。设目标次数期望为E：出现3概率1/6贡献0；出现4、5、6概率1/2贡献1+E；出现1、2概率1/3贡献E。故E=1/2+(5/6)E，解E=3。
2. 更一般地，停止面集合概率为p、被计数且不停止的事件概率为q，重复独立试验中计数期望是q/p。若两事件重合或过程依赖历史，须重新定义停止轮是否计入，不能机械套比值。

易错点与面试表达

如果把“重复出现的点数也记录”改成只统计不同点数，答案会不同；需确认计数口径。

第36题：n个椭圆最多分几块

完整题面：n个椭圆最多能将平面划分成几个区域？

答案：2n²−2n+2。

概念补课：与矩形题相同，每加入一条闭合曲线，新增区域数等于新曲线被切成的段数。两椭圆最多相交4次，第k个椭圆最多被切成4(k−1)段。

先识别模型

椭圆和矩形的递推相同，但两条椭圆最多只有4个交点。

逐步推导

1. 第一个椭圆产生2个区域。
2. 第k个椭圆最多与前面k−1个椭圆各交4次。
3. 新增区域数为4(k−1)。
4. 求和得到2+4(1+…+n−1)=2n²−2n+2。

推导补全：把关键一步展开

1. 两条不重合椭圆边界交点至多4个，可把一个椭圆仿射化为圆，再代入另一个二次方程得到至多四个交点；最大分割使用横截交点。下面的两两相交构造保证既有边界连通，此时新边界每被切出一段就增加一个区域。递推只从第二个椭圆开始，R₁=2不能误写为R₀+0。
2. 上界可达的一种构造是多条中心相同、半轴长度相同而方向不同的非圆椭圆，任意两条可有4个横截交点；再微扰去掉多重交点。故Rₙ=2+4×n(n−1)/2，而非仅仅一个未证明可达的上界。

易错点与面试表达

相切、三曲线共点会减少区域；题目问最大值，所以采用一般位置。

第37题：累计和超过1时最后一个数的期望

完整题面：每次均匀随机取[0,1]中的一个数，累计和大于1时停止，求停止时最后一个抽到的数的期望。

答案：2−e/2。

概念补课：最方便的状态是“离1还剩多少额度”r。下一数u若大于r就越线并停止；若u≤r，剩余额度更新为r−u。

先识别模型

这是第10题的“最后增量”版本。把历史压成“离1还剩多少额度”r，可以写出一维积分递推。

逐步推导

1. 定义f(r)为剩余额度r时，最终越线样本的期望。
2. 下一数u≤r则从剩余r−u继续；u>r则停止并得到u，所以\(f(r)=\int _{0}^{r}f(r-u)du+\int _{r}^{1}u du\)。
3. 换元并求导得到\(f'(r)=f(r)-r\)；边界\(f(0)=1/2\)，故\(f(r)=1+r-e^{r}/2\)。
4. 初始剩余额度r=1，代入得\(f(1)=2-e/2\)。

推导补全：把关键一步展开

1. 换元v=r−u后，\(\int_0^r f(r-u)\,du=\int_0^r f(v)\,dv\)。另一项\(\int_r^1u\,du=(1-r^2)/2\)；求导因此是f′=f−r，而不是f′=−f−r。边界r=0时下一样本必越线，均值1/2。
2. 解得f(r)=1+r−eʳ/2后，初态是剩余额度恰为1，因此直接代r=1，不能像第20题再对r从0到1平均。第20和37题方程相同，但初始状态处理不同，恰好都得到2−e/2。

易错点与面试表达

第10题停止总和的期望是e/2，本题最后抽样值的期望是2−e/2，两者不同；与本题数值相同的是第20题。

第38题：1×2骨牌铺满2×n地板

完整题面：用n个1×2的砖铺满2×n的地板，有几种铺法？

答案：Fₙ₊₁。

概念补课：递推要按最左边怎么铺分类，并保证互斥且无遗漏。最左列竖放一块后剩n−1列；横放一块时下面也必须横放，剩n−2列。

先识别模型

这是最经典的局部递推：最左边只可能放一块竖砖或两块横砖。

逐步推导

1. 竖放一块后剩2×(n−1)棋盘。
2. 横放必须成对出现，剩2×(n−2)棋盘。
3. 所以Tₙ=Tₙ₋₁+Tₙ₋₂。
4. T₀=T₁=1，故Tₙ=Fₙ₊₁。

推导补全：把关键一步展开

1. 最左上格若竖放，下方同列随之占满，剩余宽度n−1；若横放，左下格也只能横放，否则出现无法覆盖的缺口，故一次占掉两列。两类互斥且穷尽，才得到二阶递推。
2. T₀=1代表空棋盘存在一种“什么都不铺”的方案，它是递推需要的单位元；若误设0，会让T₂错误。滚动变量实现只需O(n)时间、O(1)额外空间，但大n时数值位数和大整数成本也会增长。

易错点与面试表达

不同教材对F₁、F₂的编号不同，答案最好同时写递推和初值。

第39题：记录偶数、1或3清空、5停止

完整题面：反复投公平骰子，只记录偶数；出现1或3时清空记录，出现5时停止，求停止时平均记录了几个偶数。

答案：1。

概念补课：状态\(F(k)\)表示当前记录k个偶数时的最终期望。首步分析分三类：偶数让k加1，1或3重置为0，5立即停止并兑现当前k。

先识别模型

清空操作使过程重置到状态0，不能把它当作普通“直到5出现”的几何分布。

逐步推导

1. 记录偶数的概率为1/2，清空概率为1/3，停止概率为1/6。
2. 设当前记录k个偶数，写出F(k)=k/6+F(0)/3+F(k+1)/2。
3. 猜测\(F(k)=ak+b\)。比较k的系数得\(a=1/6+a/2\)，所以a=1/3；令k=0并用b=F(0)，有\(b=b/3+(a+b)/2\)，代入a后得b=1，即F(0)=1。

推导补全：把关键一步展开

1. 除了解线性函数，还可倒看终止前最后一段：忽略偶数轮，把1、3、5视为分隔符；最后一个分隔符前的偶数段，其长度几何分布，分隔符概率1/2，因此段长均值(1/2)/(1/2)=1。终止分隔符是5与段长独立。
2. 线性式F(k)=k/3+1也可解释：当前k条记录只有在下一个非偶数是5时才保留，这一概率为(1/6)/(1/2)=1/3；当前记录贡献k/3，未来新记录的期望为1。

易错点与面试表达

记录的偶数不是累计总数；出现1或3会清空此前记录。

第40题：公平骰子第一次出现重复

完整题面：反复投一个公平六面骰子，直到某个面已经出现过两次，平均要投多少次？

答案：1223/324≈3.7747。

概念补课：若T是第一次重复时的投掷次数，\(T>k\)表示前k次仍互不相同。尾和把期望转成这些“还没停”的概率之和，不必先求T恰等于每个值的概率。

先识别模型

第一次重复是生日碰撞问题，尾和公式最简洁。

逐步推导

1. T大于k表示前k次骰子都互不相同。
2. 尾概率依次为\(P(T>0)=P(T>1)=1\)，以及\(5/6\)、\(5\cdot 4/6^{2}\)、\(5\cdot 4\cdot 3/6^{3}\)、\(5\cdot 4\cdot 3\cdot 2/6^{4}\)、\(5!/6^{5}\)。
3. 第7次前必定重复，所以把这些项相加，得到\(1223/324\approx 3.7747\)。

推导补全：把关键一步展开

1. 精确尾和为1+1+5/6+20/36+60/216+120/1296+120/7776。最后一项是前6次全部不同的概率6!/6⁶=120/7776；P(T>7)=0。求和为1223/324。
2. 对m种等概率结果，\(\mathbb E[T]=\sum_{k=0}^m(m)_k/m^k\)，其中 \((m)_k\)为下降阶乘，空乘积为1。题目若改成非均匀骰子，需逐个累加不同序列的概率，不能再只用下降阶乘。

易错点与面试表达

“某个指定面出现两次”和“任意面出现重复”是两个不同问题。

第41题：7球放5盒，非空盒子期望

完整题面：将7个球随机放入5个盒子，平均有多少个盒子非空？

答案：5[1−(4/5)⁷]≈3.9514。

概念补课：为每个盒定义指标Ij：非空记1，空记0。非空盒总数是这些指标之和；一个球进某盒虽影响其他盒，但期望相加不要求独立。

先识别模型

盒子是否非空适合用指标变量；相关性不妨碍期望相加。

逐步推导

1. 某个指定盒子为空的概率是(4/5)⁷。
2. 它非空的期望指标是1−(4/5)⁷。
3. 五个盒子相加，得到5[1−(4/5)⁷]≈3.9514。

推导补全：把关键一步展开

1. 非空盒总数记\(K=\sum_j I_j\)，对每个盒，所有7球都避开的概率是(1−1/5)⁷。线性期望只对每个Iⱼ取平均，绝不需要把不同盒是否非空当作独立。
2. 一般n球入m盒有E[K]=m[1−(1−1/m)ⁿ]，它不超过min(m,n)。n很小时约为n，n远大于m时趋近m；用这两个极限检验公式的方向。

易错点与面试表达

若问恰好r个非空盒子，则不能只用期望线性性，要用容斥或占位数。

第42题：累计和超过1就归零的最优停止

完整题面：每次均匀随机取[0,1]并累加；理性的人可以随时停止并以当前和为分数，但如果累计和超过1则得0分。求最优策略下的平均得分。

答案：(√2−1)e^(√2−1)≈0.62678。

概念补课：\(V(x)\)表示当前和为x时按最优策略能拿到的期望。停止拿x；继续抽u时只有u≤1−x不会爆掉，因此继续价值是\(\int _{x}^{1}V(t)dt\)。

先识别模型

这是连续抽样的最优停止。当前累计和高到某个阈值后停止，低于阈值则继续。

逐步推导

1. 当前和为x时，停止价值是x，继续价值是\(\int_x^1V(t)\,dt\)。
2. Bellman方程是\(V(x)=\max\{x,\int _{x}^{1}V(t)dt\}\)。设x≥a时停止；在临界点a，继续后落在t≥a便停止，因此\(a=\int _{a}^{1}t dt=(1-a^{2})/2\)，解得\(a=\sqrt{2}-1\)。
3. 阈值以下选择继续，故\(V(x)=\int _{x}^{1}V(t)dt\)，求导得\(V'(x)=-V(x)\)。结合V(a)=a，得到\(V(x)=ae^{a-x}\)和\(V(0)=ae^{a}\)。
4. 所以最优平均得分为(√2−1)e^(√2−1)≈0.62678。

推导补全：把关键一步展开

1. 阈值策略不能只凭直觉猜完就停。构造V(x)=ae^(a−x)（x<a）和V(x)=x（x≥a），再逐段代回Bellman式验证：x≥a时继续值(1−x²)/2≤x；x<a时V(x)>a>x，且积分恰等于V(x)。
2. 边界a来自a²+2a−1=0，仅正根√2−1在[0,1]中。最终V(0)=aeᵃ≈0.62678，高于一次抽样就拿走的期望1/2且小于1，符合取值边界。

易错点与面试表达

阈值a不是最终答案；a是“何时停”的界，V(0)才是初始平均得分。

第43题：周三出生的男孩

完整题面：老王有两个孩子，其中一个是星期三出生的男孩，求另一个孩子也是男孩的概率。

标准“至少一个周三男孩”模型答案：13/27。

概念补课：条件概率的分母是“能让我们收到这条信息”的家庭。每个孩子有2种性别×7种生日=14种类型；两个孩子按出生顺序区分，共14²种有序类型。

先识别模型

这是信息机制版本的条件概率题。先明确是随机选家庭，还是随机指出某个孩子。

逐步推导

1. 标准家庭模型中，每个孩子有14种性别×星期类型。
2. 至少一个周三男孩的家庭数为14²−13²=27。
3. 两个都是男孩且至少一个周三男孩的家庭数为7²−6²=13。
4. 概率为13/27。

推导补全：把关键一步展开

1. 两个孩子按出生顺序区分，否则不能把男女与女男折成一个等概率状态。补集计数的27=196−169；分子13=49−36，其中49只考虑两个都是男孩的星期组合。
2. 若父亲是先看两个孩子再按某个偏好挑一句话告诉你，报告机制会改变似然P(听到这句话|家庭)。贝叶斯分母应对该报告事件求和；题面不交代机制时应并列说明13/27与1/2分别对应的模型。

易错点与面试表达

若先随机指定一个孩子并知道他是周三男孩，另一个孩子性别仍独立，答案是1/2。

第44题：分状态夏普率都高，整体一定高吗

完整题面：策略A在高波动市场和低波动市场中的夏普率都高于策略B，A在全市场的夏普率一定高于B吗？

答案：不一定。

概念补课：忽略无风险利率时，夏普率是平均收益除以标准差。混合状态后，\(\text{总方差}=\text{平均组内方差}+\text{组间均值方差}\)，后一项可能反转排序。

先识别模型

夏普率的分母是波动，不是均值；合并分组时还会增加“状态均值之间的波动”。

逐步推导

1. 合并方差=组内方差的加权平均+组均值之间的方差。
2. 给出反例：两个状态各占一半。B在两状态的均值/标准差都为2/1，因此条件和整体夏普率都是2。
3. A在两状态的均值/标准差分别为100/40与1/0.4，条件夏普率都为2.5，高于B。
4. A合并均值50.5，总方差\((40^{2}+0.4^{2})/2+(100-1)^{2}/4=3250.33\)，整体夏普率约\(50.5/57.01=0.886\)，反而低于B。

推导补全：把关键一步展开

1. 全方差公式可直接从二阶矩推出：\(\mathbb E[R^2]=\sum_sw_s(\sigma_s^2+\mu_s^2)\)，减去总体均值μ²，得到\(\sum_sw_s\sigma_s^2+\sum_sw_s(\mu_s-\mu)^2\)。第二项来自状态切换，条件夏普率并未包含它。
2. 反例里A的组内方差均值是(1600+0.16)/2=800.08，组间方差为99²/4=2450.25，总和3250.33。此题比较相同观察口径和状态权重；若频率、杠杆或成本不同，还须先统一指标定义。

易错点与面试表达

回答时最好给出状态权重、条件均值和条件方差；只说“辛普森悖论”还不够。

第45题：细菌最终灭绝概率

完整题面：细菌每小时有25%概率死亡、25%概率保持1个、50%概率分裂成2个；初始1个细菌，求最终灭绝概率。

答案：1/2。

概念补课：每个后代会独立复制同样的未来。若一条谱系灭绝概率为q，生2个子代后两条都灭绝的概率是q²，生1个则是q。

先识别模型

这是Galton–Watson分枝过程。灭绝概率是子代生成函数的最小不动点。

逐步推导

1. 子代数为0、1、2的概率分别是1/4、1/4、1/2，生成函数f(s)=1/4+s/4+s²/2。
2. 若一个细菌最终灭绝，则它的每个子代谱系都必须灭绝，所以q=f(q)。
3. 代入得\(q=1/4+q/4+q^{2}/2\)，即\((2q-1)(q-1)=0\)，两个根为1/2与1。灭绝概率取[0,1]内最小不动点，所以q=1/2；根1只是方程形式上恒有的解。
4. 平均子代数1.25>1只说明存在正概率永不灭绝。

推导补全：把关键一步展开

1. 为什么选最小根？令q₀=0，\(q_{t+1}=f(q_t)\)，\(q_t\) 表示到第t代已经灭绝的概率。序列从0单调增加且不超过任何[0,1]内不动点，极限正是最小不动点；因此不是在两个根中随意选1/2。
2. 从m个独立初始细菌开始，所有谱系都灭绝才是总灭绝，概率qᵐ=2⁻ᵐ。若个体共享同一随机环境而并不独立，幂乘法和原生成函数递推都可能失效。

易错点与面试表达

不要因为期望子代数大于1就断言灭绝概率为0；随机分枝仍可能一开始就死亡。

第46题：100次抛硬币最长连续正面

完整题面：连续投100次公平硬币，最长连续正面的期望长度大概是多少？

面试说约6；精确期望约5.99178。

概念补课：游程是连续相同结果的一段，如THHHT含长度3的正面游程。最长游程L也是非负整数，可用\(\mathbb E[L]=\sum_{k\ge1}P(L\ge k)\)；难点转为逐个算是否出现过k连正面。

先识别模型

最长连续正面是游程问题。log₂100只给数量级，精确期望要跟踪当前末尾连续长度。

逐步推导

1. 固定阈值k，令\(a_t(j)\)表示投完t次、从未达到k连正面、且末尾恰有j个连续正面的概率，j=0,…,k−1。
2. 下一次反面时\(a_{t+1}(0)=\frac12\sum_j a_t(j)\)；下一次正面时\(a_{t+1}(j)=a_t(j-1)/2\)，达到k的路径不再保留。
3. 所以\(P(L_{100}\ge k)=1-\sum_j a_{100}(j)\)，再用尾和\(\mathbb E[L]=\sum_{k\ge1}P(L_{100}\ge k)\)。
4. 精确结果约5.99178，面试可说约6并说明这是近似。

推导补全：把关键一步展开

1. 初始a₀(0)=1，其余为0。每个k都独立运行一次避免k连正面的有限状态递推；超过阈值的路径被删除而非回到0，最后剩余总概率才是P(L<k)。
2. 100次中L≤100，因此尾和可明确求到k=100，得到精确有理数而非无穷截断近似。小样本n=1时E[L]=1/2，n=4时27/16，可用于检验实现的转移和尾和下标。

易错点与面试表达

不能直接把log₂100当成期望；连续段之间会重叠，且尾部有明显概率质量。

第47题：两个2和八个1的随机删减

完整题面：有2个数字2和8个数字1；每次等可能选一个当前数字，选到2就把它减为1，选到1就删除。平均多少次后刚好没有2？

答案：47/6。

概念补课：马尔可夫状态只保留影响未来的最少信息。这里无需记顺序，只记还有a个2和b个1；每步先付出1次操作，再按两类数字所占比例进入下一状态。

先识别模型

这是有限状态马尔可夫递推，关键是区分“2被选中变1”和“1被选中被删”。

逐步推导

1. 状态(a,b)表示有a个2、b个1。
2. 抽到1以b/(a+b)进入(a,b−1)。
3. 抽到2以a/(a+b)进入(a−1,b+1)。
4. 边界\(E(0,b)=0\)。先解一枚2：\(E(1,b)=1+[b/(b+1)]E(1,b-1)\)，归纳得\(E(1,b)=(b+2)/2\)。
5. 再用\(E(2,b)=1+[b/(b+2)]E(2,b-1)+[2/(b+2)]E(1,b+1)\)，从E(2,0)=5/2归纳得\(E(2,b)=5/2+2b/3\)。
6. 代入b=8得47/6≈7.8333。

推导补全：把关键一步展开

1. 归纳的代数可写为：假设E(2,b−1)=5/2+2(b−1)/3，且E(1,b+1)=(b+3)/2，代入原递推并通分，即得到E(2,b)=5/2+2b/3。b=0必须单独处理，因为抽到1的分支概率为0。
2. 递推按势2a+b排序是无环的：抽到2后2(a−1)+(b+1)=2a+b−1，抽到1后也减1。因此可以自底向上或记忆化求解；这也说明题目不会发生无限步不结束的循环。

易错点与面试表达

如果把2选中后直接删除，或者停止条件改成所有数字都消失，都是另一道题。

第48题：1到2ⁿ−1的二进制1总数

完整题面：将1到2ⁿ−1的所有整数写成二进制，一共出现多少个“1”？

答案：n·2ⁿ⁻¹。

概念补课：把0也写成n位二进制后，0到2ⁿ−1恰好是全部长度n的0/1串。固定一位时，其余n−1位任取，所以该位为1的串有2ⁿ⁻¹个。

先识别模型

按二进制位计数，不要逐个整数展开。

逐步推导

1. 0到2ⁿ−1正好是全部n位二进制串。
2. 固定任意一位，恰有2ⁿ⁻¹个串在该位为1。
3. 共有n位，总数n·2ⁿ⁻¹。
4. 去掉全零串不会改变“1”的总数。

推导补全：把关键一步展开

1. 所有n位比特串共有2ⁿ个，固定某位为1后其余n−1位有2ⁿ⁻¹种组合；按位先数，再对n个位求和，每一个1恰被计数一次。这里数的是符号出现次数，不是含有1的整数个数。
2. n=1时区间只有1，公式给1；n=3时1到7的popcount为1、1、2、1、2、2、3，和为12。去掉0无影响，但若也去掉2ⁿ−1则需额外减n。

易错点与面试表达

若区间不是完整的2次幂边界，就不能直接使用每一位一半的对称性。

第49题：100个骰子点数和被7整除

完整题面：投100个公平六面骰子，求点数总和被7整除的概率。

答案：1/7+1/(7·6⁹⁹)。

概念补课：模7只记录除以7后的余数0～6。骰子点数1～6恰覆盖所有非零余数；当前余数非0时，六个点数中正好一个能补成0。

先识别模型

模7递推只需维护“当前和模7为0”的概率，不必维护全部7个状态。

逐步推导

1. 设pₙ为n个骰子和模7为0的概率。
2. 若上一轮余数非0，六个点数中恰有一个能补成0，所以pₙ₊₁=(1−pₙ)/6。
3. 递推平衡点满足\(p=(1-p)/6\)，所以是1/7。令\(q_{n}=p_{n}-1/7\)，便有\(q_{n+1}=-q_{n}/6\)。
4. 初值p₁=0，即q₁=−1/7，所以\(p_{n}=1/7+(-1)^{n}/(7\cdot 6^{n-1})\)。
5. n=100时为1/7+1/(7·6⁹⁹)，几乎等于1/7。

推导补全：把关键一步展开

1. 递推不要求六个非零余数等可能。给定任意上一余数r≠0，恰一个骰面能补到0，条件概率均为1/6；给定r=0，下一个骰面没有0，条件概率为0。对这两类平均就足够。
2. 可把初值统一取p₀=1，再得pₙ=1/7+(6/7)(−1/6)ⁿ。n=1给0、n=2给1/6、n=100给正的小修正；奇偶交替来自递推斜率为−1/6。

易错点与面试表达

“几乎是1/7”是数值近似，严格答案还带一个指数小修正。

第50题：随机排列后删除下降项

完整题面：将n个互不相同的数随机打乱排成一列；从左往右扫描，只保留大于此前所有数的元素，平均留下几个数？

答案：Hₙ=1+1/2+…+1/n。

概念补课：一个数留下来等价于它比原排列中所有更早的数都大，这叫记录最大值。调和数Hn只是\(1+1/2+\ldots +1/n\)的简写。

先识别模型

扫描后留下的是前缀最大值，也叫记录值。

逐步推导

1. 第k个位置被保留，当且仅当它大于前面k−1个数。
2. 随机排列中，前k个数的最大值等可能出现在这k个位置中的任意一个，所以概率1/k。
3. 定义保留指标并相加，期望为Hₙ=1+1/2+…+1/n。
4. Hₙ约为log n+γ，说明保留数量增长很慢。

推导补全：把关键一步展开

1. 第k项是否刷新纪录只取决于前k项的相对顺序。它们的最大值位置均匀，故概率1/k；指标之间即便有依赖，期望求和仍成立。不能把保留下来的数量当作最长递增子序列长度。
2. 自然对数近似Hₙ=ln n+γ+O(1/n)，可用积分夹逼ln(n+1)≤Hₙ≤1+ln n说明增长速度。以n=100为例H₁₀₀≈5.187，远小于通常相邻上升次数约50。

易错点与面试表达

若题意只是“与原序列紧邻的前一个数比较”，留下的是上升位置而非记录值，答案会不同；本文采用作者答案Hₙ所对应的前缀最大值口径。

第51题：100根火柴的非对称取法博弈

完整题面：有100根火柴，先手每次可以取1根或7根，后手每次可以取2根或3根，取到最后一根的人获胜，谁必胜？

答案：后手必胜。

概念补课：模3只关心除以3的余数。先手动作1和7都等价于模3取1；在首轮对齐后，后手取2可让一整轮合计取掉3的倍数。

先识别模型

这是一个带不同取数集合的组合博弈，后手维护模3不变量。

逐步推导

1. 先手第一次取1或7后，后手取3，使剩余变成96或90，都是3的倍数。
2. 之后先手取1或7，在模3下都等价于取1。
3. 后手固定取2，把剩余数恢复成3的倍数。
4. 不断重复，最终后手拿到最后一根。

推导补全：把关键一步展开

1. 检查末局合法性：后手每轮后留3的正倍数给先手。若只剩3，先手只能取1，后手取2直接获胜；若先手可以取7，则剩余至少9，取7后至少还余2，后手取2仍合法。
2. 首轮特别取3是为把100减到模3为0的状态；后续固定取2是另一条规则。若误把首轮也写成取2，会留下97或91，模3为1，不再满足所维护的不变量。

易错点与面试表达

要说明取不出7时的末局规则；在通常“只能取剩余数量以内”的规则下，后手的固定回复仍然合法。

第52题：四枚硬币能否变成边长2正方形

完整题面：有4枚硬币，初始放在单位正方形四个顶点。每一步任选两枚，把其中一枚关于另一枚作中心对称移动。能否经过有限次操作让4枚硬币成为边长2正方形的四个顶点？

答案：不能。

概念补课：两个整数模2相同就是奇偶相同。整数点按(x奇偶,y奇偶)分四类；移动\(P'=2Q-P\)中2Q坐标为偶数，所以P′与P奇偶类相同。

先识别模型

中心对称移动保持每枚硬币的坐标奇偶类，这是一个模2不变量。

逐步推导

1. 初始单位正方形顶点分别属于(0,0)、(1,0)、(1,1)、(0,1)四种奇偶类。
2. P关于Q中心对称后P′=2Q−P，模2下P′与P相同。
3. 所以四枚硬币始终各占一个奇偶类。
4. 整数坐标的边长2正方形四顶点属于同一奇偶类，和初始状态矛盾。

推导补全：把关键一步展开

1. 目标正方形即使允许旋转也无法规避：任一边为整数向量(a,b)，边长2要求a²+b²=4。整数解仅为(±2,0)、(0,±2)，所以顶点间坐标差全为偶数，四顶点必属同一奇偶类。
2. 所有移动保持整数坐标，因此无需额外假设目标必须轴对齐；轴对齐是长度方程推出的结果。给四枚硬币分别标号后，每枚奇偶类始终固定，更不会因互换名字而消除矛盾。

易错点与面试表达

不变量是逐枚硬币保持的，不是只看四枚硬币整体的质心；目标正方形默认顶点仍在整数格点上。

第53题：环上随机游走走完所有n个点

完整题面：圆周上有n个点，从一个点出发，每次等可能移动到相邻点，平均多少步能走遍所有点？

答案：n(n−1)/2。

概念补课：环上每次只走相邻点，已访问集合始终是一条连续弧。已有k点时，下一次扩张相当于在线段内游走直到从任一端跨出。

先识别模型

环上随机游走的已访问集合始终是连续弧段，可以逐次计算“扩张一个新点”的等待时间。

逐步推导

1. 刚访问到k个连续点且位于端点时，把两侧未访问邻点看成吸收边界−1和k。
2. 从端点对应的0出发，简单随机游走到任一边界的期望时间是(0+1)(k−0)=k。
3. 从1个点扩张到2个点耗时1，从2到3耗时2，依此类推。
4. 总期望为1+2+…+(n−1)=n(n−1)/2。

推导补全：把关键一步展开

1. 把已访问k点标为0到k−1，外侧未访问邻点视为−1和k。从i出发的退出时间满足h(i)=1+[h(i−1)+h(i+1)]/2及h(−1)=h(k)=0，解为h(i)=(i+1)(k−i)，在新访问的端点i=0处恰为k。
2. 每次访问新点后必然位于已访问弧的一端，所以每一阶段都能使用同一个端点初态。最后扩张k=n−1时，两侧边界其实对应同一个尚未访问点，但首次退出这段弧仍是首次抵达该点，期望n−1不变。

易错点与面试表达

这不是独立地等待每个点首次出现；已访问区域的连续性才是可以递推的原因。

第54题：2n个数找最大值和最小值

完整题面：给定一个包含2n个数的数组，能否用少于3n次比较找出最大值和最小值？

答案：可以，3n−2次比较，且最优。

概念补课：单独找最大、最小各要2n−1次。配对法让第一次比较同时给两条证据：胜者不可能是最小，败者不可能是最大。

先识别模型

同时找最大值和最小值时，先让一次比较同时产生一个局部大者和一个局部小者。

逐步推导

1. 2n个数两两比较，n次比较得到n个局部大者和n个局部小者。
2. 全局最大值只可能在局部大者中，再比较n−1次。
3. 全局最小值只可能在局部小者中，再比较n−1次。
4. 总计n+(n−1)+(n−1)=3n−2次。

推导补全：把关键一步展开

1. 上界要计数到每一项：n对初比、n个胜者找最大n−1次、n个败者找最小n−1次；n=1时只比较一次，公式3n−2=1也正确。若元素个数N为奇数，经典最优界为⌈3N/2⌉−2。
2. 更严格的下界按“排除最大候选”和“排除最小候选”两类证据算。必须分别排除N−1个，合计2N−2项；对手可让只有两个从未比较的元素互比时同时产生两项新证据，这至多发生N/2次，其余比较至多产生一项。因此至少(2N−2)−N/2=3N/2−2次。

易错点与面试表达

若只问“少于3n”，给出构造即可；若问最优性，可用对手论证：至少先用n次比较让2n个元素都获得一次胜/负分类，之后仍有n个从未输过的最大候选和n个从未赢过的最小候选；两组各需n−1次，合计下界3n−2。