每日一题[598]和谐数

具有下列条件的$n$位十进制数称为“$n$位和谐数”:

(1) 首位为$1$;
(2) 不含$1,2,3$外的其他数字;
(3) 每个数字都至少和一个奇偶性相同的数字相邻.

则“$10$位和谐数”的个数为_______.


cover

分析与解 满足条件(2)(3)且前两位为$11,13,31,33$的$n$($n\geqslant 2$)位十进制数个数相同,记为$a_n$;满足条件(2)(3)且前两位为$22$的$n$位十进制数的个数记为$b_n$,则所求的“$10$位和谐数”的个数为$2a_{10}$.

以$11$开头的$n$位“和谐数”,第三位可能为$1,3,2$,其中第三位为$1$,$3$的和谐数各有$a_{n-1}$个;第三位为$2$的和谐数第四位仍然为$2$,共有$b_{n-2}$个,所以有$a_n=2a_{n-1}+b_{n-2}$;

再考虑以$22$开头的$n$位“和谐数”,第三位可能为$1,3,2$,其中第三位为$1,3$时第四位可以为$1,3$,共有$4a_{n-2}$个;第三位为$2$时,共有$b_{n-1}$个,于是有$b_n=4a_{n-2}+b_{n-1}$.

根据题意,有$a_2=b_2=1$,$a_3=2$,$b_3=1$,且有$$\begin{cases} a_n=2a_{n-1}+b_{n-2},\\ b_n=4a_{n-2}+b_{n-1},\end{cases} $$因此
屏幕快照 2016-08-05 上午10.46.41从而$2a_{10}=2014$为所求.

思考与总结 用递推的计数方式往往可以降低问题的难度.

此条目发表在每日一题分类目录,贴了标签。将固定链接加入收藏夹。

发表回复