SAUDI ARABIAN MATHEMATICAL COMPETITIONS

Let $a_i,b_i,c_i,d_i$ be the number of paths that end by $1,2,3,4$ respectively and have the sum equal to $i$. These paths all start from $1$. So it is easy to check that $$\begin{array}{rl}& a_1=1,b_1=c_1=d_1=0,a_2=b_2=c_2=d_2=0\\ & a_3=0,b_3=1,c_3=d_3=0,a_4=1,b_4=c_4=d_4=0\end{array}$$ We can visit $1$ from $2$ or $4$, visit $2$ from $1$ or $3$, visit $3$ from $2$ or $4$, visit $4$ from $3$ or $1$ then we have the following relations $$\{\begin{array}{l}{a}_n=b_{n-1}+d_{n-1}\\ b_n=a_{n-2}+c_{n-2}\\ c_n=b_{n-3}+d_{n-3}\\ d_n=c_{n-4}+a_{n-4}\end{array}$$ We have to calculate $a_{21}+b_{21}+c_{21}+d_{21}$. Denote $u_n=a_n+c_n$ and $v_n=b_n+d_n$ for $n\ge 1$ then we come to another relation $$\{\begin{array}{l}{u}_n=v_{n-1}+v_{n-3}\\ v_n=u_{n-2}+u_{n-4}\end{array}$$ We also have $u_1=1,u_2=0,u_3=0,u_4=1$ and $v_1=0,v_2=0,v_3=1,v_4=0$. Then $v_n=v_{n-3}+2v_{n-5}+v_{n-7}$ and $u_n=u_{n-3}+2u_{n-5}+u_{n-7}$.

By putting $s_n=u_n+v_n$, we get $$s_n=s_{n-3}+2s_{n-5}+s_{n-7}$$ with $s_1=1,s_2=0,s_3=1,s_4=1,s_5=1,s_6=3,s_7=1$. By direct calculation, we have $$\begin{array}{rl}& s_8=4,s_9=5,s_{10}=4,s_{11}=11\\ & s_{12}=8,s_{13}=15,s_{14}=22,s_{15}=20\\ & s_{16}=42,s_{17}=42,s_{18}=61,s_{19}=94\\ & s_{20}=97,s_{21}=167\end{array}$$ Therefore, we have $167$ paths such that the sum of numbers on these paths is equal to $21$.