Maths Olympiad Prep

Library / /46 of 61

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Canada

Problem:

Consider an equilateral triangle of side length nn, which is divided into unit triangles, as shown. Let f(n)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=5n=5. Determine the value of f(2005)f(2005).

Figure 1

Solution

Solution:

We shall show that f(n)=(n1)!f(n) = (n-1)!.

Label the horizontal line segments in the triangle l1,l2,l_{1}, l_{2}, \ldots as in the diagram below. Since the path goes from the top triangle to a triangle in the bottom row and never travels up, the path must cross each of l1,l2,,ln1l_{1}, l_{2}, \ldots, l_{n-1} exactly once. The diagonal lines in the triangle divide lkl_{k} into kk unit line segments and the path must cross exactly one of these kk segments for each kk. (In the diagram below, these line segments have been highlighted.) The path is completely determined by the set of n1n-1 line segments which are crossed. So as the path moves from the kkth row to the (k+1)(k+1)st row, there are kk possible line segments where the path could cross lkl_{k}. Since there are 123(n1)=(n1)!1 \cdot 2 \cdot 3 \cdots (n-1) = (n-1)! ways that the path could cross the n1n-1 horizontal lines, and each one corresponds to a unique path, we get f(n)=(n1)!f(n) = (n-1)!.

Therefore f(2005)=(2004)!f(2005) = (2004)!.

Figure 2

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.