HMMT-Feb 2012 guts, Problem 7

$M$ is an $8 \times 8$ matrix. For $1 \leq i \leq 8$, all entries in row $i$ are at least $i$, and all entries on column $i$ are at least $i$. What is the minimum possible sum of the entries of $M$ ?

Solution: Let $s_{n}$ be the minimum possible sum for an $n$ by $n$ matrix. Then, we note that increasing it by adding row $n+1$ and column $n+1$ gives $2 n+1$ additional entries, each of which has minimal size at least $n+1$. Consequently, we obtain $s_{n+1}=s_{n}+(2 n+1)(n+1)=s_{n}+2 n^{2}+3 n+1$. Since $s_{0}=0$, we get that $s_{8}=2\left(7^{2}+\ldots+0^{2}\right)+3(7+\ldots+0)+8=372$. $\fbox{372}$.

Answer: 372