2014 UMO Problems/Problem 6

Problem

Draw $n$ rows of $2n$ equilateral triangles each, stacked on top of each other in a diamond shape, as shown below when $n = 3$ . Set point $A$ as the southwest corner and point $B$ as the northeast corner. A step consists of moving from one point to an adjacent point along a drawn line segment, in one of the four legal directions indicated. A path is a series of steps, starting at $A$ and ending at $B$ , such that no line segment is used twice. One path is drawn below. Prove that for every positive integer $n$ , the number of distinct paths is a perfect square. (Note: A perfect square is a number of the form $k^2$ , where $k$ is an integer).

$[asy] size(200); path p1=polygon(3),p2=shift(sqrt(3)/2,1/2)*rotate(180)*polygon(3); for(int k=0;k<3;++k) {for (int j=0;j<3;++j) {draw(shift(sqrt(3)*(k+j/2),1.5*j)*p1,black+linewidth(.4)); draw(shift(sqrt(3)*(k+j/2),1.5*j)*p2,black+linewidth(.4));} } pair O=(-sqrt(3)/2,-1/2),E=(sqrt(3),0),NW=(-sqrt(3)/2,3/2),NE=(sqrt(3)/2,3/2),SE=(sqrt(3)/2,-3/2); D(O--(O+E)--(O+E+NE)--(O+2E+NE)--(O+2E+NE+SE)--(O+2E+2NE+SE)--(O+2E+2NE+SE+NW)--(O+3E+2NE+SE+NW)--(O+3E+3NE+SE+NW),black+linewidth(2)); MP("A",O,SW); MP("B",(O+3E+3NE+SE+NW),NE); draw(shift(10,0)*p1,black+linewidth(.4)); draw(shift(10,sqrt(3))*p1,black+linewidth(.4)); draw(shift(12.5,0)*p1,black+linewidth(.4)); draw(shift(12.5,sqrt(3))*p1,black+linewidth(.4)); MP("Legal Steps",(11.4,4.2)); draw((10-sqrt(3)/2,-1/2)--(10,1.5-1/2),arrow=Arrow()); draw((12.5-sqrt(3)/2,-1/2)--(12.5+sqrt(3)/2,-1/2),arrow=Arrow()); draw((10,sqrt(3)+1)--(10+sqrt(3)/2,sqrt(3)-1/2),arrow=Arrow()); draw((12.5+sqrt(3)/2,sqrt(3)-1/2)--(12.5,sqrt(3)+1),arrow=Arrow()); [/asy]$

Solution

Consider just the equilateral triangle of length $n$ made by cutting the parallelogram in half. In how many ways can you get from the SW vertex to any point on the opposite edge? Call this value $T_n$ (in fact, it doesn't matter which edgepoint you go to - there are the same number of paths). Note that $T_{n} = 2n\cdot T_{n-1}$ . Why? Consider the equilateral triangle of length $n-1$ . Note that for each edgepoint in the $n$ triangle, we can get there in $2$ ways from each of the $n$ edgepoints in the $n-1$ triangle. Now it isn't hard to see that the general formula for $T$ is $T_n = 2^nn!$ .

Now to find the number of ways to get from $A$ to $B$ . It's the sum of the number of ways to get from $B$ to each point along the diagonal, times $T_n$ . But the former is just $2n\cdot T_{n-1} = T_n$ . Therefore, the total number of paths is $T_n^2$ , which is a square number.

Note: A simpler solution, (but no general formula) is as follows: Split the parallelogram into two equilateral triangles. Then let $S_n$ be the number of walks from $A$ to each of the $n$ endpoints $e_1,...,e_n$ . Now, let $R_n$ be the number of walks over the parallelogram. Then notice that if (say) some walk ends at $e_1$ , then we can just "add" another walk from the second split triangle. So we can do this in $S_n^2$ ways. So we have $R_n=S_n^2$ , as desired.

2014 UMO (Problems • Answer Key • Resources)
Preceded by Problem 5	Followed by Last Problem
1 • 2 • 3 • 4 • 5 • 6
All UMO Problems and Solutions

Page

Toolbox

Search

2014 UMO Problems/Problem 6

Problem

Solution

See Also