令$a_n$为n位数中弹跳数的总数。令$b_{n,k}$为n位数中以k结尾的上升数总数、$c_{n,k}$为n位数中以k结尾的下降数总数, 则有
$$a_2=0, \quad b_{2,k}=k, \quad c_{2,k}=\begin{cases}10-k & k>0, \\ 9 & k=0.\end{cases}$$
注意由于$11,22,\ldots,99$既是上升数也是下降数，因此
$$a_2+\sum\limits_{k=0}^9b_{2,k}+c_{2,k}=99>90.$$
若s是以k结尾的n位数，考虑在其末尾增加一个数字d。 若s是弹跳数，则显然添加后也仍是弹跳数。 若s是上升数，则$d\ge k$时添加后才仍是上升数，否则将变为弹跳数。类似地，若s是下降数，则$d\le k$时添加后才仍是下降数，否则也将变为弹跳数。因此有
\begin{align*}
a_{n+1}&=10a_n+\sum_{k=0}^9kb_{n,k}+\sum_{k=0}^9(10-k)c_{n,k}, \\
b_{n+1,k}&=\sum_{j=0}^kb_{n,j}, \\
c_{n+1,k}&=\sum_{j=k}^9c_{n,j}.
\end{align*}
递推计算（注意所有数字都相同的数既是上升数也是下降数，需要避免重复计算）可得不超过999999的数中共有12951个非弹跳数，占1.3%， 而不超过9999999的数中共有30816个非弹跳数，占0.3%，因此结果应当是一个七位数。
再从一百万开始遍历七位数再结合上述结论即得结果$1587000$。
b=[list(range(10))]
c=[[min(10-k,9) for k in range(10)]]
s=99
i=2
r=1
while r>0.01:
b.append([sum(b[-1][j] for j in range(k+1)) for k in range(10)])
c.append([sum(c[-1][j] for j in range(k,10)) for k in range(10)])
s=s+sum(b[-1])+sum(c[-1])-9
i+=1
r=1.0*s/(10**i-1)
print i,s,r
n=1000000
s=12952
while 1.0*s/n>0.01:
n+=1
m=str(n)
k=len(m)
s=s+(all(m[i]>=m[i+1] for i in range(k-1)) or all(m[i]<=m[i+1] for i in range(k-1)))
print n
|
