Let $A$ be a set of $n$ residues $\pmod{n^{2}}$. Prove that there exists a set $B$ of of $n$ residues $\pmod{n^{2}}$ such that $A + B = \{a+b|a \in A, b \in B\}$ contains at least half of all the residues $\pmod{n^{2}}$.
Source IMO shortlist 2002
Attempt: Take at random and uniform set $B$ in $N=\{0,1,...,n^2-1\}$ such that $|B|=n$ and let $X$ counts different residues in $A+B$. Say $X_i$ is indicator variable for $i$ to be in $A+B$. Then $$X = X_0+\dots+X_{n^2-1}$$then $$E(X) = n^2\cdot E(X_0) = n^2\cdot P(X_0=1)$$ Now \begin{eqnarray}P(X_0=1) &=& P(\color{red}{0-a_1\in B}\cup \color{blue}{0-a_2\in B}\cup\dots\cup \color{gold}{0-a_n\in B})\\ &=&1- P(\color{red}{0-a_1\notin B}\cap \color{blue}{0-a_2\notin B}\cap\dots\cap \color{gold}{0-a_n\notin B})\\ &=&1- P(0-a_1\notin B)\cdot P(0-a_2\notin B)\cdots P(0-a_n\notin B)\\ &=&1- (1-P(0-a_1\in B))\cdot (1-P(0-a_2\in B))\cdots\\ &=&1- (1-P(0-a_1\in B))^n\\ &=&1- \left(1-{{n^2-1\choose n-1}\over {n^2\choose n}}\right)^n\\ &=&1- \left(1-{1\over n}\right)^n>1-{1\over e} >{1\over 2} \end{eqnarray}
So $E(X)>{n^2\over 2}$ and thus a conclusion. I'm just not sure if I may use independance here.
Actually we can avoid independence:
$$P(\color{red}{0-a_1\notin B}\cap \color{blue}{0-a_2\notin B}\cap\cdots\cap \color{gold}{0-a_n\notin B}) = P(B\subset N\setminus A_0)={{n^2-n\choose n}\over {n^2\choose n}}$$
where $A_0 = 0-A \pmod {n^2}$ and clearly $|A_0| = |A|=n$.
Since we have $${n^2-n-k\over n^2-k}\leq 1-{1\over n}$$ for each $0\leq k\leq n-1$, we have also
$${{n^2-n\choose n}\over {n^2\choose n}} = {(n^2-n)(n^2-n-1)\cdots(n^2-2n+1)\over n^2(n^2-1)\cdots(n^2-n+1)}\leq \left(1-{1\over n}\right)^n$$