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)|={\lfloor \frac{n}{2}\rfloor }^2$$ and the average of $|A\cap (A+t)|$ is $$\frac{1}{n}{\left(\lfloor \frac{n}{2}\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}⟹f(A)\le \lfloor \frac{n}{4}\rfloor -1.$$ So $g(n)\le \lfloor \frac{n}{4}\rfloor -1$.

b. Let $p\equiv 3(\mathrm{mod}4)$ be a prime, and set $$A=(F_p^{\times }{)}^2(\mathrm{mod}p)$$ We have to show that $$|(A+t)\cap A|\ge \lfloor \frac{p}{4}\rfloor -1\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}{l@{\quad \Longleftrightarrow \quad}l} 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},u\in F_p^{\times },$$ with $x\ne 0$ and $y\ne 0$, that is, $$|\begin{array}{l}u+u^{-1}t\ne 0\\ u^{-1}t-u\ne 0\end{array}⟺u^2\ne \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\ne v^2$, $$\frac{u^2+2t+u^{-2}{t}^2}{4}=\frac{v^2+2t+v^{-2}{t}^2}{4}⟺u^2-v^2=\frac{t^2}{u^2}-\frac{t^2}{v^2}⟺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⟺u^2=\pm t$). Therefore $$|A\cap (A+t)|=\frac{\frac{p-1}{2}-1}{2}=\frac{p-3}{4}=\lfloor \frac{p}{4}\rfloor -1,$$