HMMT 十一月 2009 · GEN2 赛 · 第 5 题

英文解析

5. [ 7 ] The following grid represents a mountain range; the number in each cell represents the height of themountain located there. Moving from a mountain of height a to a mountain of height b takes ( b − a )2
   time. Suppose that you start on the mountain of height 1 and that you can move up, down, left, orright to get from one mountain to the next. What is the minimum amount of time you need to get tothe mountain of height 49?
   1 3 6 10 15 21 28
   2 5 9 14 20 27 34
   4 8 13 19 26 33 39
   7 12 18 25 32 38 43
   11 17 24 31 37 42 46
   16 23 30 36 41 45 48
   22 29 35 40 44 47 49
   Answer: 212 Consider the diagonals of the board running up and to the right - so the first diagonalis the square 1, the second diagonal is the squares 2 and 3, and so on. The i th ascent is the largest steptaken from a square in the i th diagonal to a square in the i + 1 st. Since you must climb from square
   1 to square 49, the sum of the ascents is at least 48. Since there are 12 ascents, the average ascent isat least 4.
   The 1 st and 12 th ascents are at most 2, and the 2 nd and 11 th ascents are at most 3. The 6 thand 7 th ascents are at least 6, and the 5 th and 8 th ascents are at least 5. Because f ( x ) = x is convex,2
   the sum of squares of the ascents is minimized when they are as close together as possible. One possibleshortest path is then 1 → 3 → 6 → 10 → 14 → 19 → 25 → 31 → 36 → 40 → 44 → 47 → 49, whichhas ascents of size 2 , 3 , 4 , 4 , 5 , 6 , 6 , 5 , 4 , 4 , 3 , and 2. Thus, our answer is 212, the sums of the squares ofthese ascents. There are other solutions to this problem. One alternative problem involves computingthe shortest path to each square of the graph, recursively, starting from squares 2 and 3.
   Five Guys