Let $n$ be a positive integer. $f(n)$ denotes the number of $n$-digit numbers $\overline{a_1a_2\cdots a_n}$(wave numbers) satisfying the following conditions : (i) for each $a_i \in\{1,2,3,4\}$, $a_i \not= a_{i+1}$, $i=1,2,\cdots$; (ii) for $n\ge 3$, $(a_i-a_{i+1})(a_{i+1}-a_{i+2})$ is negative, $i=1,2,\cdots$. (1) Find the value of $f(10)$; (2) Determine the remainder of $f(2008)$ upon division by $13$.
Problem
Source: China south east mathematical Olympiad 2008 day2 problem 8
Tags: number theory unsolved, number theory
16.07.2013 01:10
Let $g(n)$ denotes the number of $n$-digit wave numbers satisfying $a_1<a_2$ Let $u(n)$ denotes the number of $n$-digit wave numbers satisfying $a_1>a_2$ Obviously $g(n)=u(n)\Rightarrow f(n)=g(n)+u(n)=2g(n)$ Let $v_i{k}$ denotes the number of $k$-digit wave numbers satisfying $a_1<a_2$ whose last digit is $i$. Then, $g(n)=v_1k+v_2k+v_3k+v_4k$ $Case-1:$When $k$ is even. Then, $k+1$ is odd. Whic implies that $a_{k}>a_{k+1}$ from condition $(ii)$ Obviously $v_4(k+1)=0,v_3(k+1)=v_4k,v_2(k+1)=v_4k+v_3k,$ and $v_1(k+1)=v_2k+v_3k+v_4k$ $Case-2:$When $k$ is odd. Then, $k+1$ ise even. Which implies that $a_{k}<a_{k+1}$ from condition $(ii)$. Obviously $v_1(k+1)=0, v_2(k+1)=v_1k, v_3(k+1)=v_1k+v_2k$ and $v_4(k+1)=v_1k+v_2k+v_3k$. Hence, $v_13=v_22+v_32+v_42=6$ $v_23=v_32+v_42=5$ $v_33=v_42=3$ $v_43=0$ Therefore, $g(3)= 6+5+3+0=14$ Similarly, we have $g(4)=31,g(5)=70,g(6)=157,q(7)=357$ Lemma:$g(n+1)=2g(n)+g(n-1)-g(n-2)$ Proof:We are done when $n=5,6,7$. Suppose lemma hold when for $n$. Now consider the case for $n + 1$. When $n$ is even, we have $v_4(n+1)=0, v_3(n+1)=v_4n, v_2(n+1)=v_4n+v_3n, v_1(n+1)=v_4n+v_3n+v_2n$ Then, $g(n+1)=v_1(n+1)+v_2(n+1)+v_3(n+1)+v_4(n+1)=2(v_14+v_24+v_34+v_44)+v_4n-v_2n=2g(n)+v_4n-v_2n$ Since $v_4n=v_1(n-1)+v_2(n-1)+v_3(n-1)+0=g(n-1)$ $v_2n=v_1(n-1)=v_4(n-2)+v_3(n-2)+v_2(n-2)+0=g(n-2)$ Therefore, $g(n+1)=2g(n)+g(n-1)-g(n-2)$ When $n$ is odd, we obtain same thing. When we use lemma, we see $g(9)=1782$ and $g(10)=4004$ Therefore $f(10)=2g(10)=8008$ I think $(2)$ can be proven by the lemma.
16.07.2013 13:25