Library / Indian National Mathematical Olympiad /90 of 103

Indian National Mathematical Olympiad

Combinatorics Difficulty 7.0 National Olympiad Prove it India

Problem:

Suppose the $n^{2}$ numbers $1,2,3, \ldots, n^{2}$ are arranged to form an $n$ by $n$ array consisting of $n$ rows and $n$ columns such that the numbers in each row (from left to right) and each column (from top to bottom) are in increasing order. Denote by $a_{j k}$ the number in $j$ -th row and $k$ -th column. Suppose $b_{j}$ is the maximum possible number of entries that can occur as $a_{j j}, 1 \leq j \leq n$ . Prove that
$b_{1}+b_{2}+b_{3}+\cdots b_{n} \leq \frac{n}{3}\left(n^{2}-3 n+5\right)$
(Example: In the case $n=3$ , the only numbers which can occur as $a_{22}$ are 4, 5 or 6 so that $b_{2}=3$ .)

Solution

Solution:

Since $a_{j j}$ has to exceed all the numbers in the top left $j \times j$ submatrix (excluding itself), and since there are $j^{2}-1$ entries, we must have $a_{j j} \geq j^{2}$ . Similarly, $a_{j j}$ must not exceed each of the numbers in the bottom right $(n-j+1) \times (n-j+1)$ submatrix (other than itself) and there are $(n-j+1)^{2}-1$ such entries giving $a_{j j} \leq n^{2}-(n-j+1)^{2}+1$ . Thus we see that
$a_{j j} \in\left\{j^{2}, j^{2}+1, j^{2}+2, \ldots, n^{2}-(n-j+1)^{2}+1\right\}$
The number of elements in this set is $n^{2}-(n-j+1)^{2}-j^{2}+2$ . This implies that
$b_{j} \leq n^{2}-(n-j+1)^{2}-j^{2}+2=(2 n+2) j-2 j^{2}-(2 n-1)$
It follows that
$\begin{aligned} \sum_{j=1}^{n} b_{j} & \leq (2 n+2) \sum_{j=1}^{n} j - 2 \sum_{j=1}^{n} j^{2} - n(2 n-1) \\ & = (2 n+2)\left(\frac{n(n+1)}{2}\right) - 2\left(\frac{n(n+1)(2 n+1)}{6}\right) - n(2 n-1) \\ & = \frac{n}{3}\left(n^{2}-3 n+5\right) \end{aligned}$
which is the required bound.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.