NOIP 提高 2013 第一轮 第 22 题：现有一只青蛙，初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时，下一时刻将

题目

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

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

答案

37/12

题解

考点定位

含自环的期望递推。

解题过程

令 E[k] 表示从 k 号荷叶到 1 号荷叶的期望跳跃次数，E[1]=0。对于 k≥2，先跳一次，再等概率进入 1～k，因此：

E[k]=1+(E[1]+…+E[k])/k。

把右侧的 E[k] 移到左侧，得到 E[k]=(k+E[1]+…+E[k−1])/(k−1)。逐项计算：

• E[2]=2；
• E[3]=(3+2)/2=5/2；
• E[4]=(4+2+5/2)/3=17/6；
• E[5]=(5+2+5/2+17/6)/4=37/12。

答案：37/12。

易错提醒

允许跳回当前荷叶，所以方程右侧也含 E[k]。1 号是终止状态，不能再对它套用一次跳跃的递推式。