A problem in additive combinatorics $\color{red}{\mathrm{Problem:}}$
$n\geq3$ is a given positive integer, and $a_1 ,a_2, a_3, \ldots ,a_n$ are all given integers that aren't multiples of $n$ and $a_1 + \cdots + a_n$ is also not a multiple of $n$.
Prove there are at least $n$ different $(e_1 ,e_2, \ldots ,e_n ) \in \{0,1\}^n $ such that $n$ divides $e_1 a_1 +\cdots +e_n a_n$
$\color{red}{\mathrm{My\, Approach:}}$
We can solve this by induction (not on $n$, as we can see in Thomas Bloom's answer). But I approached in a different way using trigonometric sums. Can we proceed in this way successfully?
$\color{blue}{\text{Reducing modulo $n$ we can assume that $1\leq a_j\leq n-1$}.}$
Throughout this partial approach, $i$ denotes the imaginary unit, i.e. $\color{blue}{i^2=-1}$.
Let $z=e^{\frac{2\pi i}{n}}$. Then $\frac{1}{n}\sum_{k=0}^{n-1}z^{mk} =1$ if $n\mid m$ and equals $0$ if $n\nmid m$.
Therefore, if $N$ denotes the number of combinations $e_1a_1+e_2a_2+\cdots+e_na_n$ with $(e_1,e_2,\ldots, e_n)\in\{0,1\}^n$ such that $n\mid(e_1a_1+e_2a_2+\cdots+e_na_n)$, then $N$ is equal to the following sum,
$$\sum_{(e_1,e_2,\ldots, e_n)\in\{0,1\}^n}\left(\frac{1}{n}\sum_{j=0}^{n-1}z^{j(e_1a_1+e_2a_2+\cdots+e_na_n)}\right)$$
By swapping the order of summation we get,
$$N=\frac{1}{n}\sum_{j=0}^{n-1}\prod_{k=1}^{n}(1+z^{ja_k})$$
Clearly, the problem is equivalent to the following inequality:
$$\left|\sum_{j=0}^{n-1}\prod_{k=1}^{n}(1+z^{ja_k})\right|\geq n^2\tag{1}$$
This is actually IMO shortlist $1991$ problem $13$. No proofs are available except using induction. So if we can prove inequality $(1)$, it will be a completely new proof! In fact, inequality $(1)$ is itself very interesting.
$\color{red}{\mathrm{One\, more\, idea\, (maybe\, not\, useful):}}$
Let $\theta_{jk}=\frac{ja_k\pi}{n}$ and $A=\sum_{k=1}^{n}a_k$, then we get,
$$(1+z^{ja_k})=\left(1+\cos\left(\frac{2ja_k\pi}{n}\right)+i\sin\left(\frac{2ja_k\pi}{n}\right)\right)=2\cos(\theta_{jk})(\cos(\theta_{jk})+i\sin(\theta_{jk}))$$
Therefore,
$$\left|\sum_{j=0}^{n-1}\prod_{k=1}^{n}(1+z^{ja_k})\right|=2^n\left|\sum_{j=0}^{n-1}\prod_{k=1}^{n}\cos(\theta_{jk})e^{i\theta_{jk}}\right|$$
So we get one more equivalent inequality,
$$\left|\sum_{j=0}^{n-1}\prod_{k=1}^{n}\cos(\theta_{jk})e^{i\theta_{jk}}\right|=\left|\sum_{j=0}^{n-1}e^{i\frac{\pi Aj}{n}}\prod_{k=1}^{n}\cos(\theta_{jk})\right|\geq\frac{n^2}{2^n}\tag{2}$$
$\color{red}{\text{Remark:}}$ According to the hypothesis of the question, $n\nmid A$. Therefore $e^{i\frac{\pi A}{n}}\neq\pm1$.
Can we prove this inequality?
Any hint or help will be appreciated. Thank you!
It was posted before on Math Stack Exchange
 A: I have nothing to add to the Fourier-type approach suggested in the question, but for those curious, thought it useful to outline the combinatorial solution to the problem that I know (I believe this is the same as the IMO official solution, and claim no originality).
One thing to add is that, although induction is a crucial part of the proof, we do not use induction on the problem statement itself, but rather to prove an auxiliary combinatorial fact, given below.
For each $X\subset \{1,\ldots,n\}$ we have an associated sum $S_X=\sum_{i\in X}a_i$. We want to show that there exist at least $n$ many $X$ such that $S_X\equiv 0\pmod{n}$, assuming that $a_i\not\equiv 0\pmod{n}$ for $1\leq i\leq n$ and $S_{\{1,\ldots,n\}}\not\equiv 0\pmod{n}$.
For any permutation $\pi$ of $\{1,\ldots,n\}$ consider the sequence of $n+1$ distinct sets
$$ I_0,\ldots,I_{n+1}=\emptyset, \{ \pi(1)\}, \{\pi(1),\pi(2)\},\ldots,\{\pi(1),\ldots,\pi(n)\}.$$
By the pigeonhole principle, there must exist some $i<j$ such that $I_i$ and $I_j$ induce the same sum modulo $n$. In particular, there exists some non-empty set of consecutive integers $I=\{i+1,\ldots,j\}$ such that $S_{\pi(I)}\equiv 0\pmod{n}$. Note that by our assumptions we must have $2\leq \lvert I\rvert <n$.
The key fact (which can be established by double induction on $k$ and $n$) is that, for any $n\geq 3$, if we have any collection of $1\leq k\leq n-2$ sets $X_1,\ldots,X_k\subset \{1,\ldots,n\}$, each of size $2\leq \lvert X_i\rvert<n$, then there is a permutation $\pi$ of $\{1,\ldots,n\}$ such that none of $\pi(X_i)$ are a consecutive block of integers.
Given the preceding, it is now straightforward to find $n-1$ many distinct non-empty sets $X\subset \{1,\ldots,n\}$ such that $S_{X}\equiv0\pmod{n}$ (and then the empty set gives a trivial solution, producing the requisite $n$ solutions in total).
It remains to prove the key fact. The case $k=1$ and $n\geq 3$ is obvious. Consider the bipartite graph on $[k]\times [n]$ where $i\sim x$ if either $X_i=[n]\backslash \{x\}$ or $X_i=\{x,y\}$ for some $y\in [n]$. There are clearly at most $2k<2n$ edges, and hence some element of $[n]$ has degree at most 1 in this graph, without loss of generality we can say this element is $n$, and suppose further without loss of generality that if $i\sim n$ then $i=k$.
Consider the collection of $k-1$ sets $Y_i=X_i\backslash \{n\}\subset [n-1]$ for $1\leq i<k$. By construction, these sets satisfy $2\leq \lvert Y_i\rvert<n-1$ and hence, by induction, there is a permutation $\pi$ of $[n-1]$ such that none of $\pi(Y_i)$ are consecutive blocks. If $\pi(X_k\backslash \{n\})$ is not a consecutive block, then we extend $\pi$ to a permutation of $[n]$ in the obvious way (so $\pi(n)=n$). An easy case analysis confirms that, if $\pi(X_k\backslash\{n\})$ is a consecutive block, there is always a way to extend the permutation to one on $[n]$ that 'breaks up' the block, and we are done.
A: The induction argument suggested by Thomas actually goes back to the last paper of Olson, namely J. E. Olson, A problem of Erdős on abelian groups, Combinatorica 7 (1987), 285–289.
