Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

In fact, we can even get $N + (N-1) + \cdots + 1$ residues. We do this by adding elements to $B$ one-by-one. We want to make sure that when we add the $i$th element to $B$, this expands $A+B$ by at least $n+1-i$ elements. But if, for the $i$th choice, we simply add a random element to $B$, the expected value of the increase in $|A+B|$ is at least $n+1-i$, so this is always possible.

Let $S=\{B\}$. Summing up the total number of distinct values taken by $A+B$ over all possible $B$ by complementary counting, \begin{align*} \sum_{B\in S}|A+B| = \sum_{B\in S}(N^2-|\overline{A+B}|) &=\binom{N^2}{N}N^2-\sum_{i=1}^{N^2}\sum_{B\in S}(i\not\in A+B)\\ &=\binom{N^2}{N}N^2-\sum_{i=1}^{N^2}\binom{N^2-N}{N}\\ &=\binom{N^2}{N}N^2-N^2\binom{N^2-N}{N}. \end{align*}Thus \[E(|A+B|)=N^2-N^2\frac{\binom{N^2-N}{N}}{\binom{N^2}{N}}>\frac{N^2}{2}\]since \begin{align*} \frac{\binom{N^2}{N}}{\binom{N^2-N}{N}} &=\left(\frac{N^2}{N^2-N}\right)\cdots\left(\frac{N^2-N+1}{N^2-2N+1}\right)\\ &=\left(1+\frac{N}{N^2-N}\right)\cdots\left(1+\frac{N}{N^2-2N+1}\right)\\ &>1+N\left(\frac{1}{N^2-N}+\cdots+\frac{1}{N^2-2N+1}\right)\\ &>1+N\frac{N}{N^2-N}>2. \end{align*}

Choose a random set $B$ of $n$ residues modulo $n^2$. Let $x$ be the number of residues that can be written as $a+b$. The number of ways you can choose a $b$ such that $i$ can be written as $a+b$ where $a\in A$ is $n$ since $\#(A)=n$. Therefore the probability that $i$ cannot be written in the form $a+b$ is $\left(1-\frac{n}{n^2}\right)^n$ and so the probability that $i$ can be written in the form $a+b$ is \[1-\left(1-\frac{n}{n^2}\right)^n.\] Thus $\mathbb{E}(X)=n^2\left(1-\left(1-\frac{n}{n^2}\right)^n\right)$ and so what is left to prove is that \[1-\left(1-\frac{n}{n^2}\right)^n\geq \frac12.\] This is true because $1-\left(1-\frac{n}{n^2}\right)^n=1-\left(1-\frac{1}{n}\right)^n\leq 1-\frac{1}{e}\le \frac12$ and we are done.

We can even show that the expected value $\mathbb{E}(X)=n^2\left(1-\left(1-\frac{n}{n^2}\right)^n\right)$ is greater than or equal to $\dfrac{n^2+n}{2}$ $\Longleftrightarrow 1-\left(1-\frac{n}{n^2}\right)^n \ge \dfrac{n+1}{2n}$ $\Longleftrightarrow \dfrac{n-1}{2n} \ge \left(\frac{n-1}{n}\right)^n$ $\Longleftrightarrow \dfrac{1}{2} \ge \left(\frac{n-1}{n}\right)^{n-1}$ $\Longleftrightarrow 2 \le \left(1+\frac{1}{n-1}\right)^{n-1}$ Which is true by Bernoulli's Inequality since $\left(1+\frac{1}{n-1}\right)^{n-1} \ge 1+\frac{1}{n-1}\cdot(n-1) = 2$ The last part could be done by other ways, too.

For a fixed $x\in\mathbb{Z}/n^2\mathbb{Z}=:Z$, and a random $b\in Z$, the probability that $x\in b+A$ is clearly $n/n^2=1/n$. Thus, if we choose each $n$ elements of $B$ randomly one at a time (this is different than choosing $B$ randomly), the size of the $B$ we get is at most $n$, and the probability that $x\in B+A$ is $1-(1-1/n)^n\ge 1/2$. Thus, if the probability that any element $x$ is in $B+A$ is at least $1/2$, then the expected size of $B+A$ is at least $n^2/2$, so we're done.

Consider a randomly chosen set $B$ with $|B| = n$ and $B \subseteq Z$. We will show that \[\sum_{k \in A + B} 1 \ge \frac{1}{2}n^2.\]We consider the sets $A' = \{a_1 - a_2 \mid a_1, a_2 \in A\}$ and $B' = \{b_1 - b_2 \mid b_1, b_2 \in B\}$. Clearly, these sets each contain at most $n^2$ elements, meaning that $|A' \cap B'| \le n^2$. This means that we have at most $n^2$ quadruples $(a_1, a_2, b_1, b_2)$ such that $a_1 - a_2 = b_1 - b_2$, or equivalently, $a_1 + b_2 = a_2 + b_1$. We call quadruples satisfying this property reinforcing. Since there are $n^4$ possible pairs $(a_1, a_2, b_1, b_2)$ with $a_1, a_2 \in A$ and $b_1, b_2 \in B$, the probability that any given one of these quadruples is reinforcing is less than or equal to $\frac{1}{n^2}$. Since the pair $(a_1, a_2)$ is included in $n^2$ of these quadruples, the expected number of quadruples that $(a_1,a_2)$ is included in that are reinforcing is less than or equal to $\frac{n^2}{n^2} = 1$. Thus, for any $c \in A + B$, the expected value of the number of times it can be expressed as $a+b$ for $a \in A$ and $b \in B$ is less than or equal to $2$. Now, we observe that \[2\mathbb{E}\left[\sum_{k \in A + B} 1\right] = \mathbb{E}\left[\sum_{k \in A + B} 2\right] \ge \sum_{a \in A, b \in B} 1 = n^2,\]and we are done by the probabilistic method.

Let $A=(a_1, .., a_n)$. Randomly choose $n$ distinct residues for $B$. If $k$ is not in $A+B$ that means $k-a_1, k-a_2, ..., k-a_n$ (all taken mod $n^2$) were all not chosen for $B$, which has a probability of $\frac{{n^2-n\choose n}}{{n^2\choose n}}$ of occurring. Thus the probability that an individual residue is in $A+B$ is $1-\frac{{n^2-n\choose n}}{{n^2\choose n}}>\frac{1}{2}$ (since $\frac{{n^2\choose n}}{{n^2-n\choose n}}>(1+\frac{1}{n})^n>2)$, so by linearity of expectation we're done.

Let $A=\{a_1,a_2,\ldots,a_n\}$. We will randomly pick a set of residues $B=\{b_1,b_2,\ldots,b_n\}$, and we will show that $E[|A+B|] \geq \frac{n^2}{2}$. Take a residue $c$ mod $n^2$. The chance that $c-a_i$ is not equal to one of the $b_i$'s is $1-\frac{1}{n}$. This means that the chance $c$ is not in $A+B$ is $(1-\frac{1}{n})^n$, so the chance $c$ is in $A+B$ is $1-(1-\frac{1}{n})^n$. Multiplying by all $n^2$ residues, we get that $E[|A+B|] = n^2-n^2(1-\frac{1}{n})^n$. It remains to show this is at least $\frac{n^2}{2}$. This is equivalent to showing that $(1-\frac{1}{n})^n \leq \frac{1}{2}$ for all positive integers $n$. This is obvious for $n=1$, so assume $n>1$. Taking reciprocals gives $(1+\frac{1}{n-1})^n \geq 2$. In fact, we can show that $(1+\frac{1}{n-1})^{n-1} \geq 2$, since $1+\frac{1}{n-1}$ is increasing for $n \geq 2$ and $(1+\frac{1}{2-1})^{2-1}=2$. This proves the desired inequality.

Fix $A$ and consider a random set for $B$. For some value $x$, there are $n$ elements that could be in $B$ in order for $x$ to be in $A+B$. The probability that none of these values is in $B$, which is also the probability $x$ is not in $A+B$, is \[ \left( 1 - \frac{n}{n^2} \right)^n = \left( 1 - \frac{1}{n} \right)^n < \frac{1}{e} < \frac12 .\]Therefore, $x$ is in $A+B$ with more than $\frac12$ probability, so there must be a $B$ such that $A+B$ has $\frac{n^2}{2}$ values.

Fix a residue $i$. Note that for every single element in $A$, there is exactly one corresponding residue such that $a + b \equiv i$. Hence, there are actually $n$ elements that we can put in $B$ to get equivalence. We will use this fact to calculate the sum. \newline \newline From this, the probability that a particular residue $\pmod n^2$ isn't covered by some $a + b$ is thus $\left(1 - \frac{1}{n} \right)^n$. Hence the probability it is covered is $1 - \left(1 - \frac{1}{n} \right)^n$. Then the expected number of elements that are covered is $$n^2 \left(1 - \left(1 - \frac{1}{n} \right)^n \right), $$which we can easily check satisfies the desired amount. In fact, we get the better bound of $\frac{e - 1}{e}$.

This bound is ridiculously weak. Fix $A$ and consider a random set $B$. We will compute the expected value of the number of residues which are not in $A+B$. By Linearity of Expectation, this is equal to $N^2$ times the probability that an arbitrary residue mod $N^2$ is not in $A+B$—WLOG let it be $1$. Observe that there are $\binom{N^2}{N}$ choices of $B$ unconditionally. There are also $N$ residues $r$ such that there exists an element $a \in A$ with $a+r \equiv 1 \pmod{N^2}$, so there are $\binom{N^2-N}{N}$ choices of $B$ such that $r \not \in A+B$. We now compute: \begin{align*} \frac{\binom{N^2-N}{N}}{\binom{N^2}{N}}&=\frac{N^2-N}{N^2}\cdot \frac{N^2-N-1}{N^2-1}\cdots \frac{N^2-2N}{N^2-N}\\ &\leq \left(\frac{N^2-N}{N^2}\right)^{N+1}\\ &=\left(1-\frac{1}{N}\right)^{N+1}\leq \frac{1}{e}. \end{align*}Therefore, for a random set $B$ with $A$ fixed, the expected number of residues mod $N^2$ which are not in $A+B$ is at most $\tfrac{N^2}{e}$. This implies that there exists some set $B$ of $N$ residues such that $A+B$ contains at least $N^2\tfrac{e-1}{e}>N^2/2$ residues mod $N^2$. $\blacksquare$

Take some random set $B$. Then, the probability that any residue is in $A+B$ is \[1-\left(1-\frac{1}{N}\right)^N > 1-\frac{1}{e} > \frac{1}{2}\]thus, by linearity of expectation the number of valid residues is $>\frac{1}{2}$, so by pigeonhole there exists some set $B$ which covers at least half the residues.

Nothing new here, but since I liked the problem, I will post my solution. Choose $B$ at random. Then a number $t$ is not in $A+B$ if all numbers $t-a_i$ are not in $B$, so the probability this happens in $\frac {\binom {n^2-n}{n}}{\binom{n^2}{n}}<\frac{1}{2}$ (calculations are omitted) . Hence, the expected number of the missing residues is less than $\frac{n^2}{2}$, so we are done.

For any value $x$, $x\notin A+B$ if and only if $x-B$ is disjoint from $A$. The probability that they are disjoint for a random choice of $B$ is \[\tfrac{\tbinom{n^2-n}{n}}{\tbinom{n^2}{n}}=\frac{(n^2-n)(n^2-n-1)\dots (n^2-2n+1)}{n^2(n^2-1)\dots (n^2-n+1)}.\]It suffices to show that is less than one-half. Indeed, \[\frac{(n^2-n)(n^2-n-1)\dots (n^2-2n+1)}{n^2(n^2-1)\dots (n^2-n+1)}<\left(\frac{n-1}{n}\right)^n<\frac{1}{e}<0.5\]

Fix $A$ and randomly choose set $B$ of $N$ residues. Set $A+B$ doesn't include number $x$ iff $A$ doesn't include any of $N$ numbers $x-b$ for $b\in B,$ which has probability $$\frac{\binom{N^2-N}{N}}{\binom{N^2}{N}}=\prod_{i=0}^{N-1} \frac{N^2-N-i}{N^2-i}\leq \left( \frac{N-1}{N}\right) ^N<\frac 1e<\frac 12.$$In particular, the expecting size of $A+B$ is at least $\frac{N^2}{2},$ so the conclusion follows.

$n=1$ and $n=2$ are trivial. Assume $n\geq3$ from now on. Main Claim: For all positive integers $n\geq3$, we have $$2{n^2-n\choose n}\leq {n^2\choose n}$$(I promise this will be relevant later). Multiplying this by $n!(n^2-n)!(n^2-2n)!,$ it becomes $$2((n^2-n)!)^2\leq (n^2)!(n^2-2n)!$$Cancelling as much as possible, this is $$2(n^2-2n+1)(n^2-2n+2)\cdots (n^2-n)\leq (n^2-n+1)(n^2-n+2)\cdots (n^2).$$Rewrite this as $$\frac{n^2}{n^2-n}\cdot \frac{n^2-1}{n^2-n-1}\cdots \frac{n^2-n+1}{n^2-2n+1}\geq 2.$$Note that $x/(x-n)\geq 1+\frac{1}{n}$ for all $x\leq n^2$, so $$\frac{n^2}{n^2-n}\cdot \frac{n^2-1}{n^2-n-1}\cdots \frac{n^2-n+1}{n^2-2n+1}\geq (1+\frac{1}{n})^n\geq 2,$$which shows the claim. Consider choosing the set $B$ randomly. Now, consider the probability that a residue $r$ with $0\leq r\leq n^2-1$ appears in the set $A+B\pmod{n^2}$. Since there are $n$ elements in $A$, if any of $n$ corresponding elements appear in $B$, then $r$ appears in $A+B\pmod{n^2}$. Hence, the probability that $r$ appears is $$1-\frac{{n^2-n\choose n}}{{n^2\choose n}},$$so the expected number of distinct residues is $$n^2(1-\frac{{n^2-n\choose n}}{{n^2\choose n}}).$$However, due to our main claim, $$n^2(1-\frac{{n^2-n\choose n}}{{n^2\choose n}})\geq \frac{1}{2}n^2,$$so we are done.

Fix $A$ and choose $B$ randomly with uniform probability. The probability that a residue $x$ is not in $A+B$ is \[ \frac{\binom {n^2-n}{n}}{\binom{n^2}{n}} < \left(1-\frac{1}{n}\right)^n. \]Furthermore, we bound the probability that $x$ is in $A+B$ as below: \[ 1- \left(1-\frac{1}{n}\right)^n > 1-\frac{1}{e} > \frac{1}{2}. \]Thus, by Linearity of Expectation, the expected number of residues contained in $A+B$ (mod $N^2$) is greater than $\frac{N^2}{2}$, so there exists $B$ such that number of residues contained in $A+B$ (mod $N^2$) is greater than $\frac{N^2}{2}$, and we are done.

For any fixed $A$, the probability some residue $r$ is not in $A + B$ is \[ p = \frac{\dbinom{n^2 - n}{n}}{\dbinom{n^2}{n} } = \frac{(n^2 - n)(n^2 - n - 1) \cdots (n^2 - 2n + 1)}{n^2(n^2 - 1)\cdots (n^2 - n + 1)} \]Now, notice the fractions \[ \frac{n^2 - n}{n^2}, \frac{n^2 - n - 1}{n^2 - 1}, \ldots, \frac{n^2 - 2n + 1}{n^2 - n + 1} \]are all less than or equal to $\frac{n-1}{n}$, so \[ p \le \left(\frac{n-1}{n} \right)^n = \left( 1 - \frac{1}{n} \right)^n < \frac{1}{e} < \frac{1}{2}\] By LOE, the expected number of residues in $A+B$ is equal to $n^2(1 - p)$, which is greater than $\frac{n^2}{2}$, so there must exist some set of $B$ for which $A + B$ contains at least $\frac{n^2}{2}$ residues.

One of the peaks of a GLOBAL problem, though incredibly easy the problem literally screams expected value Select B randomly with replacement; we have $$\forall c\in Z,c\notin A+B\Leftrightarrow\forall b\in B,c-b\not\in A;\quad P(c-b \not\in A)= 1 - \frac1n\Rightarrow P(\text{omit element})=\left( 1 - \frac1n \right)^n < \frac 1e < \frac12,$$meaning there's some B where $<\frac{n^2}2$ elements are omitted, as desired. $\blacksquare$ also i added those hints on arch so dont think that i literally copied the exact same thing as arch, i infact made the hint from this

Suppose not. Let's choose one element of $B$ at a time. On each move, since there are at least $\frac12 N^2$ residues left, by LoE there is some element $b$ that can get $A+b$ to have at least $\frac12 N$ new elements. Obviously this $b$ won't be already in $B$, so we get $\frac12 N\cdot N=\frac12 N^2$, contradiction.

Let us fix $A$, and pick $B$ randomly. We can prove that the expected value of $|A + B|$ is $\geq \frac{1}{2} n^2$. Note that for some element in $|A + B| x$, and some element $a$ in $A$, there is only one element $b$ in $B$ that satisfies $a + b \equiv x$. $\newline$ Then the probability that some element in $Z$ is not covered by $|A + B|$ is $(1 - \frac{1}{n})^n$, because for every $n$ elements in $A$, there is a $1 - \frac{n}{n^2}$ chance that there isn't an element in $B$ that adds up to the element in $Z$. $\newline$ Then $(1 - \frac{1}{n})^n \ge \frac{1}{e}$ (apparently), so taking the complement, we get $1 - \frac{1}{e} \ge \frac{1}{2}$, so we are done.

Clearly the probability that a residue is covered is $1-\left(1-\frac{1}{n} \right)^{n}$, so the $\mathbb{E[X]} = n^2\left(1- \left(1-\frac{1}{n}\right)^n \right) > n^2\left(\frac{e-1}{e}\right)>\frac{n^2}{2}$.

It suffices to prove that $E[|A + B|] \ge \frac{1}{2} n^2.$ Fixing $A$, an element $i \in Z$ is in $A + B$ if $\exists a \in A$ s.t $i - a \in B.$ Hence the probability is, \begin{align*} 1 - \dfrac{\binom{n^2 - n}{n}}{\binom{n^2}{n}} &= 1 - \prod_{i = 0}^{n-1} \frac{n^2 - n - i}{n^2 - i} \\ &\ge 1 - (\frac{n^2 - n}{n^2})^n \\ &= 1 - (1 - \frac{1}{n})^n. \end{align*}Observe that $(1 - \frac{1}{n})^n$ is a monotonic increasing function and let $y = \lim_{x \to \infty } (1 - \frac{1}{x})^x.$ Then, \begin{align*} \ln(y) &= \lim_{x \to \infty} \ln (1 - \frac{1}{x})^x \\ &= \lim_{x \to \infty} \frac{\ln(1 - \frac{1}{x})}{1/x} \\ &= \lim_{x \to \infty} \frac{\dfrac{1/x^2}{1 - \frac{1}{x}}}{-1/x^2} \\ &= \lim_{x \to \infty} -\frac{1}{1 - \frac{1}{x}} = -1 \\ y &= \frac{1}{e}. \end{align*}Hence, \begin{align*} E[|A + B|] &= n^2 (1 - (1 - \frac{1}{n})^n) \\ &\ge n^2(1 - \frac{1}{e}) \ge \frac{n^2}{2}. \end{align*}So we are done by PhP.

We want to prove that $\Pr(x\not\in (A+B))<\frac12$. We see that $\Pr(x\not\in (A+B))=\frac{\binom{n^2-n}{n}}{\binom{n^2}{n}}=\prod_{k=0}^{n-1}\frac{n^2-n-k}{n^2-k}<(1-\frac{1}{n})^n<\frac1e<\frac12$, as desired.