5. $[7]$ The following grid represents a mountain range; the number in each cell represents the height of the mountain 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, 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 ?
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+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 is at least 4 .

The 1st and 12th ascents are at most 2, and the 2nd and 11th ascents are at most 3. The 6 th and 7 th ascents are at least 6 , and the 5 th and 8 th ascents are at least 5 . Because $f(x)=x^{2}$ 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 \rightarrow 3 \rightarrow 6 \rightarrow 10 \rightarrow 14 \rightarrow 19 \rightarrow 25 \rightarrow 31 \rightarrow 36 \rightarrow 40 \rightarrow 44 \rightarrow 47 \rightarrow 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 .