2
$\begingroup$

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:enter image description here

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.)

$\endgroup$
2
  • 2
    $\begingroup$ Other people have solved the problem, so I'll make a pedantic comment about notation here, in the hopes that it may prevent confusion if you need to talk about graph theory later on. The word path usually carries the meaning that you are not allowed to repeat vertices (so we would not consider 1252 a path in the graph you've given, since it repeats 2). If you're allowed to repeat vertices, that is usually called a walk. This distinction is particularly important because counting walks of length $n$ is easy (as the answers here show), but counting paths of length $n$ is hard. $\endgroup$
    – Gregory J. Puleo
    Nov 28, 2014 at 18:20
  • $\begingroup$ I didn't know that (well, I thought I did, but it's no use if you don't remember on time!) Thanks, I'll make sure to keep that in mind. $\endgroup$
    – Soham Chowdhury
    Nov 29, 2014 at 1:49

2 Answers 2

Reset to default
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is brilliant. Accepting, thanks! $\endgroup$
    – Soham Chowdhury
    Nov 28, 2014 at 9:23
3
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .