$\color{red}{\mathbf{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}{\mathbf{My Approach\!:}}$

We can solve this by induction (not on $n$, as one can see in the answer provided by Thomas Bloom given in the link below). But I approached it 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}$$

Can we prove this inequality? Any hint or help will be appreciated. Thank you!

$\color{red}{\mathrm{Update:}}$ 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,


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$.

Also posted on Mathoverflow

The only combinatorial solution using induction is available here.

  • 1
    $\begingroup$ @Peter yeah, we can take $n\geq 3$. $\endgroup$
    – ShBh
    Commented Jul 9, 2020 at 18:19
  • 2
    $\begingroup$ (+1) Nr. 18, I wanted to use the pigeonhole-principle , but I could not establish a proof yet. $\endgroup$
    – Peter
    Commented Jul 9, 2020 at 18:20
  • 6
    $\begingroup$ Now posted to MO, mathoverflow.net/questions/365527/… with no notice to either site. Please don't do that. $\endgroup$ Commented Jul 13, 2020 at 12:06
  • 1
    $\begingroup$ This result and the combinatorial proof given in Mathoverflow have to be refered to: -J.E. Olson, A Problem of Erdos on abelian groups, Combinatorica 7(3) (1987) 285-289 $\endgroup$ Commented Jul 14, 2020 at 22:52
  • 2
    $\begingroup$ This is a solid approach (one that works well in many situations). The next key observation is that the summand corresponding to $j=0$ is very large (it equals $2^n$ in the notation of equation (1)). So it suffices to prove, say, that every other summand is less than $(2^n-n^2)/(n-1)$ in absolute value. $\endgroup$ Commented Jul 8, 2023 at 19:03


You must log in to answer this question.