2014 UMO Problems/Problem 6
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).
Consider just the equilateral triangle of length 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 (in fact, it doesn't matter which edgepoint you go to - there are the same number of paths). Note that . Why? Consider the equilateral triangle of length . Note that for each edgepoint in the triangle, we can get there in ways from each of the edgepoints in the triangle. Now it isn't hard to see that the general formula for is .
Now to find the number of ways to get from to . It's the sum of the number of ways to get from to each point along the diagonal, times . But the former is just . Therefore, the total number of paths is , which is a square number.
A simpler solution, (but no general formula) is as follows: Split the parallelogram into two equilateral triangles. Then let be the number of walks from to each of the endpoints . Now, let be the number of walks over the parallelogram. Then notice that if (say) some walk ends at , then we can just "add" another walk from the second split triangle. So we can do this in ways. So we have , as desired.
|2014 UMO (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All UMO Problems and Solutions|