NOIP 提高组初赛 · NOIP 2013 提高组初赛试题 第 22 题

现有一只青蛙，初始时在 $n$ 号荷叶上。当它某一时刻在 $k$ 号荷叶上时，下一时刻将等概 率地随机跳到 $1, 2, \dots, k$ 号荷叶之一上，直至跳到 $1$ 号荷叶为止。当 $n = 2$ 时，平均一共跳 $2$ 次；当 $n = 3$ 时，平均一共跳 $2.5$ 次。则当 $n = 5$ 时，平均一共跳_________次。 

注意：如果你的答案要求输出分数，请输出 a/b 的形式，且保证为最简分数。

这题考期望递推。拿到题先设E(k)为从k跳到1的平均次数，利用全期望公式列出递推式E(k)=1+(1/k)ΣE(i)，然后从已知E(2)=2、E(3)=2.5顺推即可。

学生最容易把递推式记错成E(k)=1+ΣE(i)（忘记除以k）或者在代入时把E(1)当成1而不是0，导致后面数字全跑偏。另外，题目明确要求输出最简分数a/b，很多同学习惯直接写小数3.08或37/12不检查约分，这在机考里是直接丢分的。

这道题考查概率与期望，核心是建立递推关系并逐步计算。期望的定义是随机变量取值的概率加权平均，而本题中青蛙从k号荷叶跳到1~k号荷叶的概率各为1/k，因此从k出发再回到1的平均步数，等于‘当前这一步’加上‘下一站期望的平均值’。用符号记E(k)为从k跳到1的平均次数，则E(k)=1+(1/k)×(E(1)+E(2)+…+E(k))。因为已经跳到1就停止了，所以E(1)=0。把E(1)=0代入得到简化递推：E(k)=1+(1/k)×(E(2)+…+E(k-1))，或者写成E(k)=(k-1+E(k-1)+E(k-2)+…+E(2))/k。题目给了两个样例：n=2时平均跳2次，n=3时平均跳2.5次，正好可以用来验证递推。先算E(2)=1+(1/2)×E(1)=1+0=1？不对，这里要注意：从2号荷叶跳到1或2，跳到2还要再跳一次，所以E(2)=1+(1/2)×E(1)+(1/2)×E(2)，解出来E(2)=2，与题目一致。再用这个递推算E(3)=1+(1/3)×(E(1)+E(2)+E(3))，代入E(1)=0、E(2)=2，解得E(3)=2.5，也吻合。接下来就是机械但必须准确的代数运算：E(4)=1+(1/4)×(0+2+2.5+E(4))，移项得3.5+E(4)=4E(4)，所以E(4)=3.5/3=7/6？等等，这里容易算错，正确做法是把E(4)移到左边：E(4)=1+(1/4)(E(2)+E(3)+E(4))，即E(4)=1+(1/4)(2+2.5+E(4))=1+(1/4)(4.5+E(4))，两边乘4：4E(4)=4+4.5+E(4)，得3E(4)=8.5，所以E(4)=8.5/3=17/6。最后求E(5)：E(5)=1+(1/5)(E(2)+E(3)+E(4)+E(5))=1+(1/5)(2+2.5+17/6+E(5))。先把前面三项通分：2=12/6，2.5=15/6，加起来是43/6，再加E(5)得(43/6+E(5))，乘1/5再加1：E(5)=1+(1/5)(43/6+E(5))=1+43/30+(1/5)E(5)。移项：E(5)-(1/5)E(5)=30/30+43/30=73/30，即(4/5)E(5)=73/30，所以E(5)=73/30×5/4=73/24？这里又算错了，重新核对：E(2)=2=12/6，E(3)=2.5=15/6，E(4)=17/6，三者之和=12+15+17=44，除以6得44/6=22/3。代入E(5)=1+(1/5)(22/3+E(5))=1+22/15+(1/5)E(5)，移项得(4/5)E(5)=1+22/15=37/15，所以E(5)=37/15×5/4=37/12。答案是37/12，已经是最简分数。