2014 UMO Problems/Problem 6
Problem
Draw 
rows of 
equilateral triangles each, stacked on top of each other in a diamond shape, as
shown below when 
. Set point 
as the southwest corner and point 
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 and ending at , such
that no line segment is used twice. One path is drawn below. Prove that for every positive integer ,
the number of distinct paths is a perfect square. (Note: A perfect square is a number of the form 
,
where 
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]](http://latex.artofproblemsolving.com/b/a/2/ba215e2558be399cc0e57326ebe439ccfbde21aa.png)
Solution
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 | ||
