$\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*

6more comments