China Southeastern Mathematical Olympiad

(1) When $n\ge 2$, if $a_1<a_2<\overline{a_1{a}_2\cdots a_n}$ is classified as A class. The number of $\overline{a_1{a}_2\cdots a_n}$ is denoted by $g(n)$. If $a_1>a_2$, then $\overline{a_1{a}_2\cdots a_n}$ is classified as B class. By symmetry, the number of such $\overline{a_1{a}_2\cdots a_n}$ is also $g(n)$. Thus, $f(n)=2g(n)$. Now we want to find $g(n)$. Denote $m_k(i)$ as the $k$-digit "A wave number" whose last digit is $i$ ($i=1,2,3,4$), then $$g(n)=\sum _{i=1}^4{m}_n(i).$$ As $a_{2k-1}<a_{2k}$, $a_{2k}>a_{2k+1}$, we have the following 2 cases. (a) When $k$ is even, $m_{k+1}(4)=0$, $m_{k+1}(3)=m_k(4)$, $m_{k+1}(2)=m_k(4)+m_k(3)$, $m_{k+1}(1)=m_k(4)+m_k(3)+m_k(2)$. (b) When $k$ is odd, $m_{k+1}(1)=0$, $m_{k+1}(2)=m_k(1)$, $m_{k+1}(3)=m_k(1)+m_k(2)$, $m_{k+1}(4)=m_k(1)+m_k(2)+m_k(3)$. It is obvious that $m_2(1)=0$, $m_2(2)=1$, $m_2(3)=2$, $m_2(4)=3$, then, $g(2)=6$. Hence, $$m_3(1)=m_2(2)+m_2(3)+m_2(4)=6,$$ $$m_3(2)=m_2(3)+m_2(4)=5,$$ $$m_3(3)=m_2(4)=3,m_3(4)=0.$$ Therefore $$g(3)=\sum _{i=1}^4{m}_3(i)=14.$$ On the other hand, since $$m_4(1)=0,m_4(2)=m_3(1)=6,$$ $$m_4(3)=m_3(1)+m_3(2)=11,$$ $$m_4(4)=m_3(1)+m_3(2)+m_3(3)=14,$$ we obtain, $$g(4)=\sum _{i=1}^4{m}_4(i)=31.$$ In the same way, we could get $g(5)=70$, $g(6)=157$, $g(7)=353$, $g(8)=793$. Then, in general, when $n\ge 5$, $$g(n)=2g(n-1)+g(n-2)-g(n-3).\stackrel{◯}{3}$$ Now we prove ③ as follows. Using mathematical induction, we are done when $n=5,6,7,8$. Suppose ③ holds when for 5, 6, 7, 8..., $n$ now consider the case for $n+1$. When $n$ is even, from (a), (b), we have $$m_{n+1}(4)=0,m_{n+1}(3)=m_n(4),$$ $$m_{n+1}(2)=m_n(4)+m_n(3),$$ $$m_{n+1}(1)=m_n(4)+m_n(3)+m_n(2).$$ As $m_n(1)=0$, then $$\begin{array}{rl}g(n+1)& =\sum _{i=1}^4{m}_{n+1}(i)\\ & =2\left(\sum _{i=1}^4{m}_n(i)\right)+m_n(4)-m_n(2)\end{array}$$ $$=2g(n)+m_n(4)-m_n(2).$$ Since $$\begin{array}{rl}{m}_n(4)& =m_{n-1}(1)+m_{n-1}(2)+m_{n-1}(3)+0\\ & =\sum _{i=1}^4{m}_{n-1}(i)=g(n-1),\end{array}$$ $$\begin{array}{rl}{m}_n(2)& =m_{n-1}(1)=m_{n-2}(4)+m_{n-2}(3)+m_{n-2}(2)+0\\ & =g(n-2).\end{array}$$ We obtain, $$g(n+1)=2g(n)+g(n-1)-g(n-2).$$ On the other hand, when $n$ is odd, $g(n+1)={\sum }_{i=1}^4{m}_{n+1}(i)$. $$\text{Since }{m}_{n+1}(1)=0,m_{n+1}(2)=m_n(1),m_n(4)=0,$$ $$\begin{array}{rl}{m}_{n+1}(3)& =m_n(1)+m_n(2),\\ m_{n+1}(4)& =m_n(1)+m_n(2)+m_n(3),\end{array}$$ then, $$\begin{array}{rl}g(n+1)& =\sum _{i=1}^4{m}_{n+1}(i)\\ & =2\sum _{i=1}^4{m}_n(i)+m_n(1)-m_n(3)\\ & =2g(n)+m_n(1)-m_n(3).\end{array}$$ Since $$m_n(1)=m_{n-1}(4)+m_{n-1}(3)+m_{n-1}(2)+0=g(n-1),$$ $$\begin{array}{rl}{m}_n(3)& =m_{n-1}(4)=m_{n-2}(1)+m_{n-2}(2)+m_{n-2}(3)+0\\ & =g(n-2).\end{array}$$ We get $$g(n+1)=2g(n)+g(n-1)-g(n-2).$$ Hence, ③ holds for $n+1$. By mathematical induction, ③ holds when $n\ge 5$. From ③, $$g(9)=2g(8)+g(7)-g(6)=1782,$$ $$g(10)=2g(9)+g(8)-g(7)=4004.$$ Thus, $$f(10)=2g(10)=8008.$$

(2) Now consider the sequence of remainders of $\{g(n)\}$ divided by 13. From ③, when $n=2,3,4,\dots ,14,15,16,17,\dots$, the corresponding remainders are 6, 1, 5, 5, 1, 2, 0, 1, 0, 1, 1, 3; 6, 1, 5, 5, ... Therefore, when $n\ge 2$, the sequence of remainders is a periodic sequence whose minimum period is 12. As $$2008=12\times 167+4,$$ we get $$g(2008)\equiv 5(\mathrm{mod}13).$$ Therefore, $$f(2008)\equiv 10(\mathrm{mod}13).$$