Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 $T_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 $T_n^2$ ways. So we have $R_n=T_n^2$, as desired.

See Also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2014_UMO_Problems/Problem_6&oldid=154030"