Applications of discrete Fourier analysis in math contests What I'm looking for are examples of applying ideas from Fourier analysis on finite groups, especially the simplest case of cyclic groups or products of cyclic groups, to problems from math competitions.
The motivation is that such Fourier-analytic methods don't require much theory, which makes them accessible to high-school students, and at the same time they can often lead to surprisingly deep results. 
Of course, there are some well-known applications of elementary flavor (e.g. Roth's theorem), but I guess what I'm looking for are clever and surprising applications to olympiad-style problems that we usually don't see in university courses on Fourier analysis.
This is a spin-off of this question that I asked recently.
 A: I do not know if the following exercise fits the bill, but I hope it does.

Ex. Let $n\geq 1$ be a natural number. We denote with $S_0$ the family of subsets of $\{1,\ldots,n\}$ whose cardinality belongs to $3\mathbb{Z}$, with $S_1$ the family of subsets of $\{1,\ldots,n\}$ whose cardinality belongs to $3\mathbb{Z}+1$, with $S_2$ the family of subsets of $\{1,\ldots,n\}$ whose cardinality belongs to $3\mathbb{Z}+2$. Prove that the maximum difference between two elements of $\{|S_0|,|S_1|,|S_2|\}$ is exactly one.

Proof. By the discrete Fourier transform, if $\omega=\exp\frac{2\pi i}{3}$ we have that $g(m)=\frac{1+\omega^m+\omega^{2m}}{3}$ equals one if $m\in 3\mathbb{Z}$ and zero if $m\in 3\mathbb{Z}+\{1,2\}$. In particular
$$|S_0| = \sum_{\substack{m\in 3\mathbb{Z}}}\binom{n}{m}=\frac{1}{3}\sum_{m=0}^{n}\binom{n}{m}(1+\omega^m+\omega^{2m})=\frac{2^n+(1+\omega)^n+(1+\omega^2)^n}{3} $$
where both $(1+\omega)$ and $(1+\omega^2)$ belong to the unit circle. In particular the absolute difference between $|S_0|$ and $\frac{2^n}{3}$ is at most $\frac{2}{3}$, and the same holds for $|S_1|$ and $|S_2|$. On the other hand $|S_0|,|S_1|,|S_2|$ are integers, and they cannot be equal since $3$ is not a divisor of $|S_0|+|S_1|+|S_2|=2^n$. The claim hence follows from $2^n\in\{-1,1\}\pmod{3}$.
