把所有的数字分成501组，其中：
第0组只含000，表示不存在能与之配对获胜的三位数字。
第500组只含500，表示需要见到两次500才能获胜。
其他数字两两一组，第n组包含$n$和$1000-n$，见过任意一组中的全部两个数字即可获胜。
现考虑两种情况：
第一种，已经见过一次500和1到499组中的k组，设此时期望还需$g(k)$次获胜，则有
$$g(k)=1+\frac{(k+1)\cdot g(k)+(k+1)\cdot 0+(998-2k)g(k+1)}{1000},$$
等式右侧表示下一次看到号牌时：
有$k/1000$的机会看到这k组中已经出现过的号牌，$1/1000$的机会看到0，这两种情况状态不变，期望仍需$g(k)$次获胜。
有$k/1000$的机会看到这k组中还没出现过的号牌，$1/1000$的机会看到500，这两种情况状态直接获胜，因此不再需要额外的次数。
有$(998-2k)/1000$的机会看到1到499组中还没出现过组别中的牌，此时看到过的组数变为$k+1$，因此期望需要$g(k+1)$次获胜。
第二种，已经见过1到499组中的k组，但还未见过500，设此时期望还需$f(k)$次获胜，那么下一次看到号牌时有$1/1000$的机会进入$g(k)$的状态，其它情况与上面类似，即有
$$f(k)=1+\frac{(k+1)\cdot g(k)+k\cdot 0+g(k)+(998-2k)f(k+1)}{1000},$$
递推计算即可得结果$40.66368097$。
注：为方便作浮点数除法和格式化输出，以下代码为Python 3：
f=g=0
for k in range(499, -1, -1):
g=((998-2*k)*g+1000)/(999-k)
f=(g+(998-2*k)*f+1000)/(999-k)
print(f"{f:.8f}")
|
