Bulgarian Mathematical Olympiad

Solution:

a.
Let $t \in \{0, 1, 2, \ldots, p-1\}$. Consider the remainders of $t - a_{i}$, $1 \leq i \leq m$ and $b_{j}$, $1 \leq j \leq n$, modulo $p$. Their number is $m + n > p$ and hence two of them are equal. Since the remainders of $t - a_{i}$ and $t - a_{j}$, $b_{i}$ and $b_{j}$, respectively, $i \neq j$, are different, it follows that $t - a_{r} \equiv b_{s} \pmod{p}$, i.e., $a_{r} + b_{s} \equiv t \pmod{p}$ for some $r$ and $s$. Since $t$ is an arbitrary remainder modulo $p$, we conclude that $k = p$.

b.
Let $A = \{a_{1}, a_{2}, \ldots, a_{m}\}$ and $B = \{b_{1}, b_{2}, \ldots, b_{n}\}$. For any two sets $X$ and $Y$ denote $X + Y = \{x + y \pmod{p} \mid x \in X, y \in Y\}$. We have to prove that $k = |A + B| \geq m + n - 1$. To do this, we may assume that $m \leq n$ and we shall use induction on $m$.

For $m = 1$ and any $n$ the statement is true, since $a_{1} + b_{i} \neq a_{1} + b_{j} \pmod{p}$ if $i \neq j$ and $|a_{1} + B| = |B| = n = 1 + n - 1$.

Suppose that the statement is true for any two sets $X$ and $Y$ such that $|X| < m$, $|X| < |Y|$ and $|X| + |Y| \leq p$. Let $|A| = m > 1$ and $|B| = n$, where $m \leq n$ and $m + n \leq p$. Then $n < p$ and hence there exists $c \notin B$. Take different $a_{1}, a_{2} \in A$. As the sequence $c + t(a_{2} - a_{1}) \pmod{p}$, $t = 1, 2, \ldots, p-1$, contains all remainders except $c$, then $b = c + t(a_{2} - a_{1}) \in B$ for some $t$. Let $t$ be the minimal number with this property. The set $A' = \{b - a_{2}\} + A$ contains the elements $b - a_{2} + a_{1}$ and $b - a_{2} + a_{2} = b$. Note that $b - a_{2} + a_{1} = c + (t-1)(a_{2} - a_{1}) \notin B$. Since $|A' + B| = |\{b - a_{2}\} + A + B|$, it is enough to prove that $|A' + B| \geq m + n - 1$.

Set $F = A' \cap B$ and $G = A' \cup B$. Since $b \in F$, $b - a_{2} + a_{1} \notin F$ and $b - a_{2} + a_{1} \in A'$, then $F$ is a proper non-empty subset of $A'$. So $B$ is a proper subset of $G$. It follows that $0 < |F| < m \leq n < |G|$. On the other hand, $m + n = |A'| + |B| = |A' \cap B| + |A' \cup B| = |F| + |G|$. Note also that $F + G \subset A' + B$ (for $f \in F$ and $g \in G$, we may assume that $g \in A'$ and then $f \in F \subset B$ implies that $f + g \in A' + B$). Thus $|A'| + |B| \geq |F| + |G|$. Then the inequalities $0 < |F| < m \leq n < |G|$, $|F| + |G| \leq p$ and the induction hypotheses imply that the statement is true for the sets $F$ and $G$. Hence

$$|A + B| = |A' + B| \geq |F + G| \geq |F| + |G| - 1 = |A'| + |B| - 1 = m + n - 1$$
which completes the induction.