Question 75
Consider the $n \times n$ "multiplication table" below. The numbers in the first column multiplied by the numbers in the first row give the remaining numbers in the table.
| 1 | 2 | 3 | $\cdots$ | $n$ |
| :---: | :---: | :---: | :---: | :---: |
| 2 | 4 | 6 | $\cdots$ | $2 n$ |
| 3 | 6 | 9 | $\cdots$ | $3 n$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$ |
| $n$ | $2 n$ | $3 n$ | $\cdots$ | $n^{2}$ |
We create a path from the upper-left square to the lower-right square by always moving one cell either to the right or down. For example, in the case $n=5$, here is one such possible path, with all the numbers along the path circled:
| 1 | 2 | 3 | 4 | 5 |
| :---: | :---: | :---: | :---: | :---: |
| 2 | 4 | 6 | 8 | 10 |
| 3 | 6 | 9 | 12 | 15 |
| 4 | 8 | 12 | 16 | 20 |
| 5 | 10 | 15 | 20 | 25 |
If we add up the circled numbers in the example above (including the start and end squares), we get 93. Considering all such possible paths on the $n \times n$ grid:
a. What is the smallest sum we can possibly get when we add up the numbers along such a path? Express your answer in terms of $n$, and prove that it is correct.
b. What is the largest sum we can possibly get when we add up the numbers along such a path? Express your answer in terms of $n$, and prove that it is correct.
| 1 | 2 | 3 | $\cdots$ | $n$ |
| :---: | :---: | :---: | :---: | :---: |
| 2 | 4 | 6 | $\cdots$ | $2 n$ |
| 3 | 6 | 9 | $\cdots$ | $3 n$ |
| $\vdots$ | $\vdots$ | $\vdots$ | $\ddots$ | $\vdots$ |
| $n$ | $2 n$ | $3 n$ | $\cdots$ | $n^{2}$ |
We create a path from the upper-left square to the lower-right square by always moving one cell either to the right or down. For example, in the case $n=5$, here is one such possible path, with all the numbers along the path circled:
| 1 | 2 | 3 | 4 | 5 |
| :---: | :---: | :---: | :---: | :---: |
| 2 | 4 | 6 | 8 | 10 |
| 3 | 6 | 9 | 12 | 15 |
| 4 | 8 | 12 | 16 | 20 |
| 5 | 10 | 15 | 20 | 25 |
If we add up the circled numbers in the example above (including the start and end squares), we get 93. Considering all such possible paths on the $n \times n$ grid:
a. What is the smallest sum we can possibly get when we add up the numbers along such a path? Express your answer in terms of $n$, and prove that it is correct.
b. What is the largest sum we can possibly get when we add up the numbers along such a path? Express your answer in terms of $n$, and prove that it is correct.