2015 年河南预赛 · 第 12 题

解答

令 $u_n$ 为由这些数码组成、没有相邻的十六或六十一的长度 $n$ 串数，辅助定义 $u_0=1$。把合法串按末位分成普通数码二、三、四、五的 $A_n$ 类，及末位一、六的 $B_n$ 类，则

故 $u_{n+2}=5u_{n+1}+4u_n$，$u_0=1,u_1=6$。设 $r_{\pm }=(5\pm \sqrt{41})/2$，解递推得

全部串共 $6^n$，且无零数码，均为 $n$ 位数。因此答案为