# Number of possibilities to cross a hexagonal lattice.

An ant walks along the line segments in the hexagonal lattice shown, from start to finish. The ant must go in the direction shown if there is an arrow, and never goes on the same line segment twice. How many different paths can the ant take?

I am not looking for an answer to this, just a hint on how to get started. I have an adjacency matrix setup, and know that I can use A^r to find possibilities for r number of lengths, but that includes retaking the same paths. How do I get over that bump?

Note: Original image here

-
What is your motivation to study such a specific problem? – Did Mar 3 '13 at 16:33
It is a problem of the week at my school. Even if I don't turn it in for that, I would like to know how to do it regardless. – DLManiac Mar 3 '13 at 18:33
After about 7 hours of working on it, it just bugs me. – DLManiac Mar 3 '13 at 18:39
Wish I could answer it as $2.4.6.8...$ – Metin Y. Mar 11 '13 at 18:46
This question has been asked before on MSE but not answered. According to comments there, the answer is 2400. It has also been posted to artofproblemsolving/Wiki/... and identified as 2012 AMC 10B Problems/Problem 25. – achille hui Mar 13 '13 at 21:54

Thanks for merico's crucial hint "4 coulmns of arrows going to the right", following is my answer.

By collapsing some of the vertices and edges, the honey comb is equivalent to following ladder graph:

Forget about the matrix expression in above figure first. Some of the edges in this ladder graph has been labeled by a number. It means that edge in the ladder graph corresponds to multiple edges in the original honey comb.

It is clear the ladder graph is composed of 3 repeating units. Figure 2 below shows the correspondence between the leftmost portion of the honey comb with the first building unit.

Each unit is composed of 2 inputs on the left, 2 outputs on the right, $2m$ forward arrows and $1$ backward arrow in the middle. One can connect the input of an unit, say $A$, to the outputs $B$ or $C$ in 3 possible manners.

As depicted in the figure 3, there are

• (figure 3a) $m + m = 2m$ ways connect to $B$ without using the backward arrow.
• (figure 3b) $m + m = 2m$ ways connect to $C$ without the backward arrow.
• (figure 3c) $m \times m = m^2$ ways connect to $C$ using the backward arrow.

For each building unit, we can summarize the number of possibilities of joining the input with the output using a $2\times 2$ matrix: $$A(m) = \begin{pmatrix}2m & 2m+m^2\\2m+m^2 & 2m\end{pmatrix}$$

In particular, for the building units $A(1)$ and $A(2)$ appear in the honey comb, we have:

$$A(1) = \begin{pmatrix}2 & 3\\3 & 2\end{pmatrix}\;\;\text{ and }\;\; A(2) = \begin{pmatrix}4 & 8\\8 & 4\end{pmatrix}$$

The purposes of these matrices and the usefulness of merico's hint boils down to a simple fact. Once one can break down a directed graph into a chain of subgraphs with output of one subgraph feeding into input of next subgraph. The counting of all possible paths from start to finish is simplified. It turns into a condition sum of number of paths conditional to what edges are taken between the subgraphs.

The computation of total number of paths $\mathcal{N}_{path}$ becomes evaluation of a matrix product of corresponding matrices and the matrix expression can be written down by inspection of the graph! This is what the mysterious matrix expression in Figure 1 for and the final result is:

$$\mathcal{N}_{path} = \begin{pmatrix}1\\1\end{pmatrix}^T \begin{pmatrix}2 & 3\\3 & 2\end{pmatrix} \begin{pmatrix}2 & 0\\0 &2\end{pmatrix} \begin{pmatrix}4 & 8\\8 & 4\end{pmatrix} \begin{pmatrix}2 & 0\\0 &2\end{pmatrix} \begin{pmatrix}2 & 3\\3 & 2\end{pmatrix} \begin{pmatrix}1\\1\end{pmatrix} = 2400$$

UPDATE

This question has been asked before on MSE but not answered. It has also been posted to artofproblemsolving and identified as 2012 AMC 10B Problems/Problem 25. According to the answer on artofproblemsolving, $\mathcal{N}_{path}\;$ is 2400.

-

You can see that since there are $4$ columns in which all arrows are going to the right, once you use one of them, you cannot go back to the left of this column. So that any path will go through exactly one arrow from each column, and between two of those, it must stay between those two columns.

Then it is not too hard to count, for any possible "consecutive" pair of those arrows, how many path there are between them.

For example, look at the paths between the $2$nd and $3$rd columns. Each one has $4$ arrows. If $N(i,j)$ is the number of path from the $i$th arrow of the $2$nd column to the $j$th arrow of the $3$rd, column, $N(1,1) = N(1,2) = 4, N(1,3) = N(1,4) = 8$ and so on (so you never have to count very far).

Then you gather these results, which allows you to easily count the number of paths from the start to any of those arrows, and finally, the number of paths from start to end.

-
(+1) for the crucial hint of the "4 coulmns of arrows going to the right". – achille hui Mar 13 '13 at 19:58

Edited.

Claim 1. For each horizontal edge of the third column of hexagons there are exactly 5 paths that traverse this edge.

Proof. If you don't use the backwards arrow in the second column you can choose among two horizontal edges each in the first and the second columns of hexagons; makes four possibilities. If you use the backwards arrow in the first column there is just one path for each horizontal edge in the third column.

Claim 2. If you don't use the backwards arrow in the center of the figure there are 1600 paths in all.

Proof. You can choose independently 20 paths to traverse the first three columns of hexagons, 4 edges to traverse the fourth column of hexagons, and 20 paths to traverse the last three columns of hexagons.

Claim 3. If you use the backward edge in the center of the figure there are 800 paths in all.

Proof. In this case the top two horizontal edges in the forth column can only be reached from the top two horizontal edges in the third column. So there are 10 paths each using one of the top two horizontal edges in the fourth column before going backwards. After traversing the backwards edge there are again $10+10=20$ possibilities to proceed. All in all this gives $2\cdot20\cdot20=800$ possibilities.

It follows that the total number of admissible paths is 2400.

-

If you don't use any of the backward arrows, there are clearly $2^2\cdot 4^3 \cdot 2^2=2^{10}=1024$ paths. You can use any subset of the three backward arrows, but each one you use reduces the number of possible paths by a factor of $2$ (for the fourth column) or $4$ (for the second and sixth columns): you can use half the forward arrows the first time you go forward across the column with the backward arrow (the ones you can reach without crossing the center row, giving a factor of $1/2$); you can use the other half the second time (an extra choice, giving a factor of either $1$ or $2$); and you can only use half the arrows when you cross the next column to the right (again, the ones you can reach without crossing the center row, giving another factor of $1/2$). So the result is $$1024 \cdot \left(1+\frac{1}{4}\right)\cdot\left(1+\frac{1}{2}\right)\cdot\left(1+\frac{1}{4}\right)=2400.$$ Specifically, there are $1024$ paths using no backward arrows, $1024$ using exactly one backward arrow, $320$ using two of them, and $32$ using all three.

-