2008 AIME II Problems/Problem 10

Revision as of 18:21, 15 April 2008 by Azjps (talk | contribs) (will finish)

Problem

The diagram below shows a $4\times4$ rectangular array of points, each of which is $1$ unit away from its nearest neighbors.

[asy] unitsize(0.25inch); defaultpen(linewidth(0.7));  int i, j; for(i = 0; i < 4; ++i) 	for(j = 0; j < 4; ++j) 		dot(((real)i, (real)j)); [/asy]

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 $m$ be the maximum possible number of points in a growing path, and let $r$ be the number of growing paths consisting of exactly $m$ points. Find $mr$.

Solution

We label our points using coordinates $0 \le x,y \le 3$, with the bottom-left point being $(0,0)$. By the Pythagorean Theorem, the distance between two points is $\sqrt{d_x^2 + d_y^2}$ where $0 \le d_x, d_y \le 3$; these yield the possible distances (in decreasing order) \[\sqrt{18},\ \sqrt{13},\ \sqrt{10},\ \sqrt{9},\ \sqrt{8},\ \sqrt{5},\ \sqrt{4},\ \sqrt{2},\ \sqrt{1}\] As these define $9$ lengths, so the maximum value of $m$ is $10$. 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 $\sqrt{18}$ length is only possible for one of the long diagonals, which can be placed in $2$ ways.

[asy] unitsize(0.25inch); defaultpen(linewidth(0.7)); dotfactor = 4; pen s = linewidth(4);  int i, j; for(i = 0; i < 4; ++i) 	for(j = 0; j < 4; ++j) 		dot(((real)i, (real)j)); dot((0,0)^^(3,3),s); draw((0,0)--(3,3));  [/asy]

Continuing,

[asy] unitsize(0.25inch); defaultpen(linewidth(0.7)); dotfactor = 4; pen s = linewidth(4); pen c = rgb(0.5,0.5,0.5); int i, j; for(i = 0; i < 4; ++i) 	for(j = 0; j < 4; ++j) 		dot(((real)i, (real)j)); dot((0,0)^^(3,3)^^(1,0),s); draw((0,0)--(3,3)); draw((3,3)--(1,0),c);  [/asy]

The rest are determined:

unitsize(0.25inch);
defaultpen(linewidth(0.7)); dotfactor = 4; pen s = linewidth(4); pen c = rgb(0.5,0.5,0.5);
int i, j;
for(i = 0; i < 4; ++i)
	for(j = 0; j < 4; ++j)
		dot(((real)i, (real)j));
dot((0,0)^^(3,3)^^(1,0)^^(2,3)^^(2,0)^^(0,2)^^(2,1)^^(0,1)^^(1,2),s); draw((0,0)--(3,3)--(1,0)--(2,3)--(2,0)--(0,2)--(2,1)--(0,1)--(1,2));
The answer is $mr = 10 \cdot 24 = \boxed{240}$. 
 (Error making remote request. Unknown error_msg)

See also

2008 AIME II (ProblemsAnswer KeyResources)
Preceded by
Problem 9
Followed by
Problem 11
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions