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


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

  • 2
    $\begingroup$ Also posted to m.se, math.stackexchange.com/questions/3750621/… with no notice to either site. Please don't do that. $\endgroup$ Jul 13 '20 at 12:05
  • $\begingroup$ I cannot see how do you prove this by induction. For the exponential sum approach, the problem is that you seem not to take into account that $a_1+\dotsb+a_n$ is not divisible by $n$, which is essential (consider $a_1=\dotsb=a_n=1$). $\endgroup$
    – Seva
    Jul 13 '20 at 13:41
  • 1
    $\begingroup$ This is not what I am saying. The problem is not that the assumption $a_1+\dotsb+a_n\not\equiv 0\pmod n$ is missing from the statement; it is that this assumption does not seem to be used - and it is impossible to prove the assertion without using this assumption. $\endgroup$
    – Seva
    Jul 13 '20 at 16:31
  • 1
    $\begingroup$ In my impression, the result is known, and probably due to Olson. $\endgroup$ Jul 14 '20 at 1:18
  • 2
    $\begingroup$ @Seva , Alapan: See the official solution on page 555. $\endgroup$ Jul 14 '20 at 16:00

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.

  • 1
    $\begingroup$ I do not know the official solution, but this is the only solution which I know. It is written, in particular, in IMO Compendium book. By the way, it works for any Abelian group of order $n$. Possibly for groups like $\mathbb{F}_p^k$ with large $k$ the bound may be improved. $\endgroup$ Jul 14 '20 at 12:13
  • $\begingroup$ Thanks Fedor! I had written this up in some personal notes a while ago, and neglected to write down where the argument came from. Now that you say it, I'm sure it must have been the IMO Compendium book itself. $\endgroup$ Jul 14 '20 at 12:46
  • 3
    $\begingroup$ See the official solution on page 555. $\endgroup$ Jul 14 '20 at 15:54

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.