Track / Stage 5 / 71 of 400 #1311 of 2604

Problem 1311

AIME late

Algebra Difficulty 5.1 Find the answer HMMT February

$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$ ?

Your answer

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Official 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$ .

Source: Omni-MATH, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.