Let
![A](/media/m/5/a/e/5ae81275ee67d638485e903bdc0e9cde.png)
be a set of
![N](/media/m/f/1/9/f19700f291b1f2255b011c11d686a4cd.png)
residues
![\pmod{N^{2}}](/media/m/c/4/b/c4b2401db2db4648e7055eadf1ee4744.png)
. Prove that there exists a set
![B](/media/m/c/e/e/ceebc05be717fa6aab8e71b02fe3e4e3.png)
of
![N](/media/m/f/1/9/f19700f291b1f2255b011c11d686a4cd.png)
residues
![\pmod{N^{2}}](/media/m/c/4/b/c4b2401db2db4648e7055eadf1ee4744.png)
such that
![A + B = \{a+b|a \in A, b \in B\}](/media/m/f/9/5/f95da7a7c29b44bb9cf325090bd53668.png)
contains at least half of all the residues
![\pmod{N^{2}}](/media/m/c/4/b/c4b2401db2db4648e7055eadf1ee4744.png)
.
%V0
Let $A$ be a set of $N$ residues $\pmod{N^{2}}$. Prove that there exists a set $B$ 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}}$.