Brazilian Math Olympiad

a.
Let $A = \{a_1, a_2, \dots, a_{\lfloor n/2 \rfloor}\}$. Consider the sum
$$\sum_{t=0}^{n-1} |A \cap (A+t)|$$
Now each element $a \in A$ appears in a set $A + t_i$ $|A| = \lfloor n/2 \rfloor$ times: choose $t_i = a - a_i$ for each $i = 1, 2, \dots, \lfloor n/2 \rfloor$. So
$$\sum_{t=0}^{n-1} |A \cap (A+t)| = \left\lfloor \frac{n}{2} \right\rfloor^2$$
and the average of $|A \cap (A+t)|$ is
$$\frac{1}{n} \left( \left\lfloor \frac{n}{2} \right\rfloor \right)^2 \le \frac{n}{4}.$$
Since $|A \cap (A+0)| = |A| > \frac{n}{4}$ is above average, there is a $t$ such that $|A \cap (A+t)|$ is below average, so
$$f(A) \le |A \cap (A+t)| < \frac{n}{4} \implies f(A) \le \left\lfloor \frac{n}{4} \right\rfloor - 1.$$
So $g(n) \le \left\lfloor \frac{n}{4} \right\rfloor - 1$.

b.
Let $p \equiv 3 \pmod 4$ be a prime, and set
$$A = (F_p^\times)^2 \pmod{p}$$
We have to show that
$$|(A+t) \cap A| \ge \left\lfloor \frac{p}{4} \right\rfloor - 1 \quad \text{for all } t \in F_p$$
Since this is clear for $t = \bar{0}$, we henceforth assume that $t \ne \bar{0}$. From now on, all equalities are in $F_p$, that is, taken modulo $p$.

We have that $x^2 \in A \cap (A+t)$ if and only if there exists $y^2 \in A$ such that
$$\begin{array}{ll} x^2 = y^2 + t & (x-y)(x+y) = t \\[1.5ex] \left| \begin{array}{l} x-y=u \\ x+y=u^{-1}t \end{array} \right. & \text{for some } u \in F_p^{\times} \\[1.5ex] \left| \begin{array}{l} x = \displaystyle\frac{u+u^{-1}t}{2} \\ y = \displaystyle\frac{u^{-1}t-u}{2} \end{array} \right. & \text{for some } u \in F_p^{\times} \end{array}$$

$$x^2 = \frac{u^2 + 2t + u^{-2}t^2}{4}, \quad u \in F_p^{\times},$$
with $x \neq 0$ and $y \neq 0$, that is,
$$\left| \begin{array}{l} u + u^{-1}t \neq 0 \\ u^{-1}t - u \neq 0 \end{array} \right. \iff u^2 \neq \pm t$$

$$\left(\frac{\pm t}{p}\right) = \left(\frac{\pm 1}{p}\right) \left(\frac{t}{p}\right) = \pm \left(\frac{t}{p}\right)$$

On the other hand, if $u^2 \neq v^2$,
$$\frac{u^2 + 2t + u^{-2}t^2}{4} = \frac{v^2 + 2t + v^{-2}t^2}{4} \iff u^2 - v^2 = \frac{t^2}{u^2} - \frac{t^2}{v^2} \iff u^2 v^2 = t^2$$
Hence, as $u^2$ runs over the non-zero quadratic residues, with exception of $\pm t$, we obtain each $x^2 \in A \cap (A+t)$ twice (observe that the case $u^2 = v^2$ is excluded since $u^2 \cdot u^2 = t^2 \iff u^2 = \pm t$). Therefore
$$|A \cap (A+t)| = \frac{\frac{p-1}{2} - 1}{2} = \frac{p-3}{4} = \left\lfloor \frac{p}{4} \right\rfloor - 1,$$