So I was looking at a few past-years' papers from the ZIO (an IOI qualifier held here in India), and I found this question:
I think this is the same as finding the number of paths of (let's take (a)) length 8 starting at vertex 4 on this graph:
1 ---- 2 ---- 3
| | |
4 ---- 5 ---- 6
| | |
7 ---- 8 ---- 9
How can this be done systematically, and (more importantly) on pen and paper? (I have an extremely inelegant answer which I don't like. I'll post it below.)
On
You can get exact formula with a little effort:
Let $a_n$ be the number of $n$ digit codes starting from corners, that is, from $1$, $3$, $7$ and $9$.
Let $b_n$ be the number of $n$ digit codes starting from sides, that is, from $2$, $4$, $6$ and $8$.
Let $c_n$ be the number of $n$ digit codes starting from center, that is, from $5$.
Note the recursing formulas for $n\geq2$:
$$ \begin{align} a_{n+1}&=2b_n\\ b_{n+1}&=2a_n+c_n\\ c_{n+1}&=4b_n \end{align} $$
Also note that $a_2=2$, $b_2=3$ and $c_2=4$; and from above formulas we get $a_3=6$, $b_3=8$ and $c_3=12$.
Therefore we get $2a_n=c_n$ and $b_{n+1}=4a_n$ for all $n\geq2$.
Finally we reach a nice recursion formula:
$$ \begin{align} a_{n+2}&=2b_{n+1}=8a_n\\ b_{n+2}&=4a_{n+1}=8b_n\\ c_{n+2}&=2a_{n+2}=16a_n=8c_n \end{align} $$
It is easy to reach exact formulas from this:
$$ \begin{align} &a_{2n}=2.8^{n-1}\\ &b_{2n}=3.8^{n-1}\\ &c_{2n}=4.8^{n-1}\\ &a_{2n+1}=6.8^{n-1}\\ &b_{2n+1}=8.8^{n-1}\\ &c_{2n+1}=12.8^{n-1} \end{align} $$
This may be written more compactly depending on your preference. Let me know if there's a need for clarification.
To do (a), you can start with $$\pmatrix{0&1&0\cr0&0&0\cr0&0&0\cr}$$ Then replace each entry with the sum of all its neighbors, $$\pmatrix{1&0&1\cr0&1&0\cr0&0&0\cr}$$ Do it again; $$\pmatrix{0&3&0\cr2&0&2\cr0&1&0\cr}$$ The eighth matrix you get this way will tell you, for each digit $d$, how many codes of length 8 there are starting with 2 and ending with $d$. So you just have to add up all the entries in the 8th matrix to get the answer.