Iranian Mathematical Olympiad

We prove the statement using the following lemmas.

Lemma 1. If $|A_i| + |A_j| = 2n + 1 - r$ for a non-negative $r$, then there exist $a_i \in A_i, a_j \in A_j$ such that $2n - 1 - r \le a_i + a_j \le 2n - 1 + r$.
Proof. Assume the contrary. Let $A_i = \{x_1 \le x_2 \le \cdots \le x_{|A_i|}\}$ and let $y_t = 2n - 1 - x_t$ be the complement of $x_t$. Since $A_j$ is non-empty, there exists $y \in A_j$.
If $y > y_1$ then we also have $y \ge y_1 + r$. Now consider the following values:
$$y_{|A_i|}, y_{|A_i|-1}, \cdots, y_2, y_1, y_1+1, y_1+2, \cdots, y_1+r$$
They are $|A_i|+r$ distinct numbers; all of them belong to $[0, 2n-1]$. Moreover $A_j$ cannot contain any of them. So the size of $A_j$ is at most $2n - (|A_i| + r)$ which is a contradiction.
If $y < y_1$ then let $t$ be the smallest index such that $y < y_t$. Indeed, we also have $y < y_t - r$. Now consider the following numbers:
$$y_{|A_i|}, y_{|A_i|-1}, \dots, y_{t+1}, y_t - r, y_t - (r-1), \dots, y_t, y_{t-1}, y_{t-2}, \dots, y_1,$$
which are $|A_i| + r$ distinct numbers and all of them belong to $[0, 2n-1]$, moreover $A_j$ cannot contain any of them. So the size of $A_j$ is at most $2n - (|A_i| + r)$ which is a contradiction.

Lemma 2. If $|A_i| + |A_j| = 2n + 1 + r$ for a non-negative $r$, then for every $2n-1-r \le s \le 2n-1+r$ there exist $a_i \in A_i, a_j \in A_j$ such that $a_i + a_j = s$.
Proof. First take a number $s \in [2n-1-r, 2n-1]$, and let $h = 2n-1-s$. $A_i, A_j$ in total at most have $2h$ elements from the set $\{s+1, s+2, \dots, 2n-1\}$. So the number of elements of $A_i, A_j$ in the interval $[0, s]$ is at least $2n+1+r-2h \ge s+2$ in total. Applying Pigeonhole principle for $s+1$ pairs $(0, s), (1, s-1), \dots, (s, 0)$ we can easily get $s$ as the sum of two elements, one from $A_i$ and one from $A_j$. The proof for $s \in [2n, 2n+r]$ is similar.

Comment 1. This means we can cover the whole interval $[2n-1-r, 2n-1+r]$ by the bi-sums of elements, one from $A_i$ and one from $A_j$.

Lemma 3. If we have $2k$ subsets such that the sum of their sizes is $k(2n + 1) + r$ for a non-negative $r$, then for every $k(2n-1) - r \le s \le k(2n-1) + r$ there exist $2k$ elements, one from each subset, whose sum is $s$.

Comment 2. This means we can cover the whole interval $[k(2n-1) - r, k(2n-1) + r]$ by the sums of elements of these $2k$ subsets.
Proof. We proceed the proof through induction $k$, with base $k=1$ being Lemma 2. As for the inductive step, we consider $A_i, A_j$ as the two subsets with minimum size among those $2k$ subsets.
If $|A_i| + |A_j| = 2n+1+r'$ for a non-negative $r'$ then $r' \le r$ and by Lemma 2 $A_i, A_j$ can cover the interval $[2n-1-r', 2n-1+r']$. Also by induction the other $2k-2$ subsets cover the interval $[(k-1)(2n-1) - (r-r'), (k-1)(2n-1) + (r-r')]$. By combining the two intervals we can cover the whole interval $[k(2n-1)-r, k(2n-1)+r]$.
If $|A_i| + |A_j| = 2n+1-r'$ for a positive $r'$ then by Lemma 1 there exist $a_i \in A_i, a_j \in A_j$ such that $2n-1-r' \le a_i + a_j = s \le 2n-1+r'$. Also by induction, the other $2k-2$ subsets cover the interval $[(k-1)(2n-1) - (r+r'), (k-1)(2n-1) + (r+r')]$. By adding $s$ to the numbers in this interval we can cover the whole interval $[k(2n-1)-r, k(2n-1)+r]$.

The statement of the problem is indeed a special case of Lemma 3 where $k = n$ and $r = 0$.