24th Korean Mathematical Olympiad Final Round

The answer is $\lfloor \frac{(n+1)(m+1)}{2}\rfloor -1$.

For a shelf $R$, let $\tilde{R}$ be the rectangular area by extending $R$ by 1 row to the top and 1 column to the left. Let us also extend the initial chessboard by 1 row to the top and 1 column to the left. We assign $-\infty$ to each of those new unit squares so that the number of shelves is preserved. For a shelf $R$, let us call the integer $h$ satisfying two conditions the height of $R$.

Claim 1: If two shelves $R_1$ and $R_2$ do not intersect, then ${\tilde{R}}_1\cap {\tilde{R}}_2=\varnothing$.

Proof of Claim 1: Let $h_1,h_2$ be the height of $R_1,R_2$ respectively. Without loss of generality, let us assume $h_1\le h_2$. If ${\tilde{R}}_1\cap {\tilde{R}}_2\ne \varnothing$, then some unit square $x$ in $R_2$ is adjacent to $R_1$ and therefore the integer in $x$ is less than or equal to $h_1$. Since $x\in R_2$, the integer in $x$ is larger than $h_2$, contradictory to the assumption that $h_1\le h_2$. This proves Claim 1.

Claim 2: If $R_1$ and $R_2$ are distinct maximal shelves smaller than the whole chessboard, then $R_1\cap R_2=\varnothing$.

Proof of Claim 2: Let $h_1,h_2$ be the height of $R_1,R_2$ respectively. Without loss of generality, let us assume $h_1\le h_2$. Suppose that $R_1\cap R_2\ne \varnothing$. Suppose a unit square $x$ in $R_2$ shares at least one point with $R_1$. If $x$ does not belong to $R_1$, then the integer in $x$ should be at most $h_1$ but since $x\in R_2$, the integer in $x$ should be larger than $h_2$, contradictory to the assumption that $h_1\le h_2$. So such $x$ belongs to $R_1$ and therefore $R_2\subseteq R_1$. However this contradicts to the assumption that $R_2$ is maximal. So Claim 2 is proved.

Claim 3: The number of shelves in the $n\times m$ chessboard is less than or equal to $\frac{(n+1)(m+1)}{2}-1$.

Proof of Claim 3: We proceed by induction on $n+m$. If $n+m=2$, then $n=m=1$ and the number of shelves is 1.

Now let us assume $n+m>2$. Let $R_1,R_2,\dots ,R_k$ be the maximal shelves strictly smaller than the whole $n\times m$ chessboard.

By Claims 1 and 2, ${\tilde{R}}_i\cap {\tilde{R}}_j=\varnothing$. By the induction hypothesis, the number of shelves contained in $R_i$ for each $i$ is at most $|{\tilde{R}}_i|/2-1$. Therefore the number of all shelves is at most $$\sum _{i=1}^k\left(\lfloor \frac{|{\tilde{R}}_i|}{2}\rfloor -1\right)\le \frac{(n+1)(m+1)}{2}-k-1.$$ So Claim 3 is proved if $k>1$. We may now assume that $k=1$. Then it is enough to show that $$\max \left(\frac{m(n+1)}{2}\cdot \frac{(m+1)n}{2}\right)-1+1\le \frac{(n+1)(m-1)}{2}-1.$$ It is easy to see this because $n\ge 1$ is equivalent to the inequality that $\frac{m+n-1}{2}\le \frac{(n+1)(m+1)}{2}-1$. This proves Claim 3.

Now it remains to show that there is an assignment of integers so that the number of shelves is exactly $\lceil \frac{(n+1)(m+1)}{2}\rceil -1$. We proceed by induction on $n+m$. It is trivial if $\max (n,m)\le 2$.

Now by symmetry let us assume that $m>2$. Let us write 1 in each unit square on the second row. For the first row, we write integers larger than 1 obtained by the induction hypothesis on a $1\times n$ chessboard. For the remaining rows, we write integers larger than 1 obtained by the induction hypothesis on a $(m-2)\times n$ chessboard.

Now the number of shelves in this assignment is $$1+\lfloor \frac{2(n+1)}{2}-1\rfloor +\lceil \frac{(m-1)(n+1)}{2}-1\rceil$$ by the induction hypothesis. This completes the proof. $\square$