Difference between revisions of "2005 Canadian MO Problems/Problem 1"
m (→See also: box) |
|||
(3 intermediate revisions by 3 users not shown) | |||
Line 4: | Line 4: | ||
[[Image:CanMO_2005_1.png]] | [[Image:CanMO_2005_1.png]] | ||
==Solution== | ==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 <math>k</math>, the path must move down and then directly across to the last triangle in row <math>k+1</math>. Therefore, there is exactly one path through any given set of last triangles. For <math>1\le m\le n-1</math>, there are <math>m</math> possible last triangles for the <math>m</math>th row. The last triangle of the last row is always in the center. Therefore, <math>f(n)=(n-1)!</math>, and <math>f(2005)=2004!</math>. | ||
+ | |||
==See also== | ==See also== | ||
*[[2005 Canadian MO]] | *[[2005 Canadian MO]] | ||
+ | |||
+ | {{CanadaMO box|year=2005|before=First Question|num-a=2}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] |
Latest revision as of 19:46, 7 February 2007
Problem
Consider an equilateral triangle of side length , which is divided into unit triangles, as shown. Let
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
. Determine the value of
.
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 , the path must move down and then directly across to the last triangle in row
. Therefore, there is exactly one path through any given set of last triangles. For
, there are
possible last triangles for the
th row. The last triangle of the last row is always in the center. Therefore,
, and
.
See also
2005 Canadian MO (Problems) | ||
Preceded by First Question |
1 • 2 • 3 • 4 • 5 | Followed by Problem 2 |