(Canada 2005) Consider an equilateral triangle with side length n, divided into unit triangles as illustrated. Let $f(n)$ be the number of paths from the triangle in the top row to the triangle at the center of the bottom row, such that adjacent triangles share a common edge, the path never revisits the same triangle, and it never goes upwards (from a lower row to a higher row). Such a path is illustrated below with $n=5$. Determine the value of $f(2012)$.

![](https://cdn.mathpix.com/cropped/2024_05_10_732985225e470d5c7305g-107.jpg?height=374&width=434&top_left_y=1708&top_left_x=802)
The application that associates with a path an $(n-1)$-tuple $\left(x_{1}, \ldots, x_{n-1}\right)$ where $x_{i}$ is the integer $x$ such that the path crosses the $i$-th horizontal line from the top at the $x$-th segment from the left. This application is clearly a bijection between the set of considered paths and the set $[1] \times[2] \times \cdot \times[n-1]$, which has cardinality $(n-1)!$. Thus, $f(2012)=2011!$.

## 4 Extremal Principle

## - 1. Minimum Principle. -

Axiom 1 (Minimum Principle). Every non-empty set of natural numbers has a minimum.

In many problems, especially in arithmetic and combinatorics, it is often useful to consider a minimal value within a certain set. If it involves natural numbers, this can be done using the minimum principle. It is rare that a problem can be solved using only this principle; in fact, it often allows one to reduce to certain special cases of a problem whose study is simpler than the general case. It often combines well with proof by contradiction: to show that an object does not exist, one assumes it does and considers, in some sense, the smallest one; then one shows that from this, one can construct an even smaller one, leading to a contradiction. This will be illustrated by exercises 2 and 3, for example. There is also an analogous principle ensuring that every non-empty and bounded set of integers has a maximum. Note, the assumption of boundedness is essential here.