Difference between revisions of "2014 UMO Problems/Problem 6"
(→Problem) |
(→Solution) |
||
Line 33: | Line 33: | ||
== Solution == | == Solution == | ||
+ | Consider just the equilateral triangle of length <math>n</math> 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 <math>T_n</math> (in fact, it doesn't matter which edgepoint you go to - there are the same number of paths). Note that <math>T_{n} = 2n\cdot T_{n-1}</math>. Why? Consider the equilateral triangle of length <math>n-1</math>. Note that for each edgepoint in the <math>n</math> triangle, we can get there in <math>2</math> ways from each of the <math>n</math> edgepoints in the <math>n-1</math> triangle. Now it isn't hard to see that the general formula for <math>T</math> is <math>T_n = 2^nn!</math>. | ||
+ | |||
+ | Now to find the number of ways to get from <math>A</math> to <math>B</math>. It's the sum of the number of ways to get from <math>B</math> to each point along the diagonal, times <math>T_n</math>. But the former is just <math>2n\cdot T_{n-1} = T_n</math>. Therefore, the total number of paths is <math>T_n^2</math>, which is a square number. | ||
== See Also == | == See Also == |
Latest revision as of 16:04, 12 February 2020
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).
Solution
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.
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 |