3 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.
\begin{tabular}{|c|c|c|c|c|}
\hline 1 & 2 & 3 & $\cdots$ & $n$ \\
\hline 2 & 4 & 6 & $\cdots$ & $2 n$ \\
\hline 3 & 6 & 9 & $\cdots$ & $3 n$ \\
\hline$\vdots$ & $\vdots$ & $\vdots$ & $\ddots$ & $\vdots$ \\
\hline$n$ & $2 n$ & $3 n$ & $\cdots$ & $n^{2}$ \\
\hline
\end{tabular}

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:
\begin{tabular}{|c|c|c|c|c|}
\hline 1 & 2 & 3 & 4 & 5 \\
\hline 2 & 4 & 6 & 8 & 10 \\
\hline 3 & 6 & 9 & 12 & 15 \\
\hline 4 & 8 & 12 & 16 & 20 \\
\hline 5 & 10 & 15 & 20 & 25 \\
\hline
\end{tabular}

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.
3 The minimum is achieved by staying on the perimeter of the grid, and the maximum by staying as close to the main diagonal as possible. To see why this is true, tilt the grid 45 degrees:
Now every path must include exactly one number from each row. The $n^{\text {th }}$ row consists of the numbers $k(n+1-k)$ for $k=1,2, \ldots, n$. As a quadratic function of $k$, this expression is greatest when $k=(n+1) / 2$, and gets smaller as $k$ gets farther from $(n+1) / 2$ in either direction. Thus the smallest number in row $n$ of our tilted grid is the number on either end of the row, which is $n$, and the largest number in row $n$ is the number closest to the center, which is $\left\lfloor\frac{n+1}{2}\right\rfloor \cdot\left\lceil\frac{n+1}{2}\right\rceil$. By staying on the perimeter of the grid, we may select the smallest entry from every row, and so accumulate the smallest possible total. By staying in the middle, we may select the largest entry from every row and accumulate the largest possible total.
All that remains is to calculate these totals in terms of $n$.
The minimum total is
$$
\begin{aligned}
(1+2+3+\cdots+(n-1))+\left(n+2 n+3 n+\cdots+n^{2}\right) & =(1+2+\cdots+(n-1))+n(1+2+\cdots+n) \\
& =\frac{n(n-1)}{2}+n \cdot \frac{n(n+1)}{2} \\
& =\frac{n\left(n^{2}+2 n-1\right)}{2} .
\end{aligned}
$$

The maximum total is
$$
\begin{aligned}
1^{2}+1 \cdot 2+2^{2}+2 \cdot 3+\cdots+(n-1) \cdot n+n^{2} & =\left(1^{2}+2^{2}+\cdots+n^{2}\right)+(1 \cdot 2+2 \cdot 3+\cdots+(n-1) \cdot n) \\
& =\frac{n(n+1)(2 n+1)}{6}+2 \cdot\left[\binom{2}{2}+\binom{3}{2}+\cdots+\binom{n}{2}\right] \\
& =\frac{n(n+1)(2 n+1)}{6}+2\binom{n+1}{3} \\
& =\frac{n(n+1)(2 n+1)}{6}+\frac{2(n-1)(n)(n+1)}{6} \\
& =\frac{n(n+1)(4 n-1)}{6}
\end{aligned}
$$
and we are finished.