Mongolian National Mathematical Olympiad

The minimum value of $a$ is
$$c = \frac{\left[ \frac{(n+1)^2}{4} \right]}{n+1} = \begin{cases} \frac{k+1}{2}, & n = 2k+1 \\ \frac{k(k+1)}{2k+1}, & n = 2k. \end{cases}$$

We observe that if the $2 \times n$ grid is given as below, the value of $a$ is not less than $c$.

$n = 2k:$

$n = 2k + 1:$

Let us show that regardless of the numbers written in the $2 \times n$ grid, we can delete one number from each column, totally $n$ numbers, so that the sum of the remaining numbers in each row is at most $c$. Let $a_1 \le a_2 \le \dots \le a_n$ be the numbers in the first row with sum $A$ and let $b_1 \le b_2 \le \dots \le b_n$ be the numbers in the second row with sum $B$.

Lemma. If $a_1 + \dots + a_{s+1} > c$ and $b_1 + \dots + b_{t+1} > c$, then $s + t \ge n$.

Proof. From the first condition we get that
$$\frac{a_1 + \dots + a_{s+1}}{s+1} > \frac{c}{s+1}.$$
Since
$$\frac{a_1 + \dots + a_n}{n} \ge \frac{a_1 + \dots + a_{s+1}}{s+1},$$
it follows that $\frac{A}{n} > \frac{c}{s+1}$. Similarly, $\frac{B}{n} > \frac{c}{t+1}$. Since $A+B=n$, we get that
$$\frac{1}{c} > \frac{1}{s+1} + \frac{1}{t+1}. \qquad (1)$$

Case: $n = 2k + 1$. Suppose that $s + t \le 2k$. Then $s + 1 + t + 1 \le 2k + 2$ and
$$\frac{2}{\frac{1}{s+1} + \frac{1}{t+1}} \le \frac{s+1+t+1}{2} \le \frac{2k+2}{2}.$$
Hence $\frac{1}{s+1} + \frac{1}{t+1} \ge \frac{2}{k+1} = \frac{1}{c}$, which contradicts (1).

Case: $n = 2k$. Suppose that $s + t \le 2k - 1$. Thus $s + 1 + t + 1 \le 2k + 1$. Similarly to the previous case we get that
$$\frac{1}{s+1} + \frac{1}{t+1} \ge \frac{1}{k+1} + \frac{1}{k} = \frac{2k+1}{(k+1)k} = \frac{1}{c},$$
which contradicts (1).

Let $s_0$ be the minimum $s$ satisfying $a_1 + \cdots + a_{s+1} > c$ and let $t_0$ be the minimum $t$ satisfying $b_1 + \cdots + b_{t+1} > c$. Then by the lemma $s_0 + t_0 \ge n$. Because of the choice of $s_0$ and $t_0$, it follows that $a_1 + \cdots + a_{s_0} \le c$ and $b_1 + \cdots + b_{t_0} \le c$. This shows that we can delete $n-s_0$ numbers from the first row and $n-t_0$ numbers from the second row so that the sum of the remaining numbers in each row is at most $c$. This completes the proof.