Growing Path
Source: AIME 2008II Problem 10
April 3, 2008
analytic geometryAMC
Problem Statement
The diagram below shows a rectangular array of points, each of which is 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 be the maximum possible number of points in a growing path, and let be the number of growing paths consisting of exactly points. Find .