2008 AIME II Problems/Problem 10
From AoPSWiki
Problem
The diagram below shows a 
rectangular array of points, each of which is 
unit away from its nearest neighbors.
Define a growing path to be a sequence of distinct points of the array with the property that the distance between consecutive points of the sequence is strictly increasing. Let 
be the maximum possible number of points in a growing path, and let 
be the number of growing paths consisting of exactly points. Find 
.
Solution
We label our points using coordinates 
, with the bottom-left point being 
. By the Pythagorean Theorem, the distance between two points is 
where 
; these yield the possible distances (in decreasing order)
As these define 
lengths, so the maximum value of is 
. For now, we assume that 
is achievable. Because it is difficult to immediately impose restrictions on a path with increasing distances, we consider the paths in shrinking fashion. Note that the shrinking paths and growing paths are equivalent, but there are restrictions upon the locations of the first edges of the former.
The 
length is only possible for one of the long diagonals, so our path must start with one of the 
corners of the grid. Without loss of generality (since the grid is rotationally symmetric), we let the vertex be and the endpoint be 
.
The 
length can now only go to 
points; due to reflectional symmetry about the main diagonal, we may WLOG let the next endpoint be 
.
From , there are two possible ways to move 
away, either to 
or 
. However, from , there is no way to move 
away, so we discard it as a possibility.
From , the lengths of 
fortunately are all determined, with the endpoint sequence being 
.
From 
, there are 
possible lengths of 
(to either 
). Thus, the number of paths is 
, and the answer is 
.
See also
| 2008 AIME II (Problems • Resources) | ||
| Preceded by Problem 9 | Followed by Problem 11 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
