# Difference between revisions of "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]$