2005 Canadian MO Problems/Problem 1

Problem

Consider an equilateral triangle of side length $n$, which is divided into unit triangles, as shown. Let $f(n)$ be the number of paths from the triangle in the top row to the middle triangle in the bottom row, such that adjacent triangles in our path share a common edge and the path never travels up (from a lower row to a higher row) or revisits a triangle. An example of one such path is illustrated below for $n=5$. Determine the value of $f(2005)$.

CanMO 2005 1.png

Solution

Define a last triangle of a row as the triangle in the row that the path visits last. From the last triangle in row $k$, the path must move down and then directly across to the last triangle in row $k+1$. Therefore, there is exactly one path through any given set of last triangles. For $1\le m\le n-1$, there are $m$ possible last triangles for the $m$th row. The last triangle of the last row is always in the center. Therefore, $f(n)=(n-1)!$, and $f(2005)=2004!$.

See also

2005 Canadian MO (Problems)
Preceded by
First Question
1 2 3 4 5 Followed by
Problem 2