Summer Problem Solving Marathon Solution #29

First we determine the length of the longest possible growing path. We do this by enumerating the distances between points. Two points in the grid can be separated by 0 to 3 units horizontally and 0 to 3 units vertically. Using the Pythagorean Theorem, that gives us the following possible distances:

√1: 0,1 and 1,0 separation
√2: 1,1 separation
√4: 0,2 and 2,0 separation
√5: 1,2 and 2,1 separation
√8: 2,2 separation
√9: 0,3 and 3,0 separation
√10: 1,3 and 3,1 separation
√13: 2,3 and 3,2 separation
√18: 3,3 separation

That's a total of 9 different distances, so the longest possible growing path would be of length 10.

Next we check to see if a length 10 path is possible, and (if it is possible) how many such paths there are. Since the movement options are more constrained when the distances are long than when they are short, we construct the path in reverse.

First we need a length √18 gap. This is possible only by moving from one corner dot to the opposite corner dot. For convenience, we label the dots (x,y), where x and y both range from 1 to 4. Then our path can start:

(1,1), (4,4)
(4,4), (1,1)
(1,4), (4,1)
(4,1), (1,4)

So there are four choices for the first pair of elements in the path.

Since the diagram is symmetric, these four choices will proceed in the same way. For convenience, we focus on the case (1,1), (4,4). From (4,4) we need a gap of √13. This requires moving 3 units in one direction and 2 in the other. There are two points that meet this requirement: (2,1) and (1,2). Symmetry is still preserved, so we focus on the case (2,1).

Next we need a gap of √10. This requires a movement of 3 units in one direction and 1 in the other. There are two points meeting this condition: (1,4) and (3,4).

However, (1,4) will not work. We next need a gap of distance √9, which requires a separation of 3 in one direction and 1 in the other. The points meeting this constraint are (1,1) and (4,4), but both of these are already in the path.

So we must proceed with (3,4). The only point of distance √9 from (3,4) is (3,1), so this move is forced. From here, we need a gap of distance √8, which requires a separation of 2 units in both directions. The only point meeting this constraint is (1,3), so this move is also forced.

Next we need a distance of √5, with separations of 2 and 1. (2,1), (3,2), and (3,4) all meet this constraint, but only (3,2) is unused, so this move is also forced.

Next we need a distance of &rdic;4, with separations of 2 and 0. (3,4) and (1,2) both meet this constraint, but only (1,2) is unused, so this move is also forced.

Next we need a distance of √2, with a separation of 1 unit in both directions. (2,1) and (2,3) meet this constraint, but only (2,3) is unused, so this move is also forced.

Finally we need a distance of √1, which requires a move of a single unit horizontally or vertically. There are four points meeting this constraint, but (3,1) is already in the path. The other three are available.

Looking back, we had 4 choices for the first move, 2 for the second, and 3 for the final. All other moves were forced. So there are a total of 4 x 2 x 3 = 24 paths of length 10.

The desired answer is then 10 x 24 = 240.