2008 AIME II Problem 10

Below is the professionally curated solution for Problem 10 of the 2008 AIME II, from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2008 AIME II solutions, or check the answer key.

All of the real AMC 8, AMC 10, AMC 12, and AIME problems in our complete solution collection are used with official legal permission of the Mathematical Association of America (MAA).

Concepts:lattice pointdistance formulaextremal argumentcasework

Difficulty rating: 3060

10.

The diagram below shows a 4×44 \times 4 rectangular array of points, each of which is 11 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 mm be the maximum possible number of points in a growing path, and let rr be the number of growing paths consisting of exactly mm points. Find mr.mr.

Solution:

The squared distance between two points of the array is a2+b2,a^2 + b^2, where aa and bb are the coordinate differences, each in {0,1,2,3}\{0, 1, 2, 3\} and not both zero. The possible values are 1,2,4,5,8,9,10,13,181, 2, 4, 5, 8, 9, 10, 13, 18 — only 99 values — so a growing path has at most 1010 points, and a path with 1010 points must use all nine distances in increasing order. Label its points P1,,P10P_1, \ldots, P_{10} so that P1P2=1P_1 P_2 = 1 and P9P10=18.P_9 P_{10} = \sqrt{18}.

Since 18\sqrt{18} is realized only by opposite corners, there are 44 ordered choices of (P10,P9).(P_{10}, P_9). Next, P8P9=13P_8 P_9 = \sqrt{13} leaves 22 choices for P8,P_8, the two neighbors of P10,P_{10}, symmetric across the main diagonal. From there the distances 10,3,8,5,2,2\sqrt{10}, 3, \sqrt{8}, \sqrt{5}, 2, \sqrt{2} force P7,P6,,P2P_7, P_6, \ldots, P_2 uniquely (for P7P_7 the alternative corner choice fails because the point needed next for P6P_6 would coincide with P9P_9 or P10P_{10}). Finally P1P_1 must be at distance 11 from P2,P_2, and 33 of its neighbors are unused. One of the resulting paths is shown below.

Hence m=10m = 10 and r=423=24,r = 4 \cdot 2 \cdot 3 = 24, so mr=240.mr = 240.

← Problem 9Full ExamProblem 11

Problem 10 in Other Years