Difference between revisions of "2005 Canadian MO Problems/Problem 1"

(Added categorization (not entirely sure about difficulty, though))
m (See also: box)
 
Line 9: Line 9:
 
==See also==
 
==See also==
 
*[[2005 Canadian MO]]
 
*[[2005 Canadian MO]]
 +
 +
{{CanadaMO box|year=2005|before=First Question|num-a=2}}
  
 
[[Category:Intermediate Combinatorics Problems]]
 
[[Category:Intermediate Combinatorics Problems]]

Latest revision as of 19:46, 7 February 2007

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