HMMT 十一月 2009 · GEN2 赛 · 第 5 题
HMMT November 2009 — GEN2 Round — Problem 5
题目详情
- [ 7 ] The following grid represents a mountain range; the number in each cell represents the height of the 2 mountain located there. Moving from a mountain of height a to a mountain of height b takes ( b − a ) time. Suppose that you start on the mountain of height 1 and that you can move up, down, left, or right to get from one mountain to the next. What is the minimum amount of time you need to get to the 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 Five Guys
解析
- [ 7 ] The following grid represents a mountain range; the number in each cell represents the height of the 2 mountain located there. Moving from a mountain of height a to a mountain of height b takes ( b − a ) time. Suppose that you start on the mountain of height 1 and that you can move up, down, left, or right to get from one mountain to the next. What is the minimum amount of time you need to get to the 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 diagonal is the square 1, the second diagonal is the squares 2 and 3, and so on. The i th ascent is the largest step taken from a square in the i th diagonal to a square in the i + 1st. 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 is at least 4. The 1st and 12th ascents are at most 2, and the 2nd and 11th ascents are at most 3. The 6th 2 and 7th ascents are at least 6, and the 5th and 8th ascents are at least 5. Because f ( x ) = x is convex, the sum of squares of the ascents is minimized when they are as close together as possible. One possible shortest path is then 1 → 3 → 6 → 10 → 14 → 19 → 25 → 31 → 36 → 40 → 44 → 47 → 49, which has 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 of these ascents. There are other solutions to this problem. One alternative problem involves computing the shortest path to each square of the graph, recursively, starting from squares 2 and 3. Five Guys