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

See also