11
$\begingroup$

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

$\endgroup$
11
  • 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, 2020 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, 2020 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, 2020 at 16:31
  • 1
    $\begingroup$ In my impression, the result is known, and probably due to Olson. $\endgroup$ Jul 14, 2020 at 1:18
  • 2
    $\begingroup$ @Seva , Alapan: See the official solution on page 555. $\endgroup$ Jul 14, 2020 at 16:00

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
3
  • 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, 2020 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, 2020 at 12:46
  • 3
    $\begingroup$ See the official solution on page 555. $\endgroup$ Jul 14, 2020 at 15:54
2
$\begingroup$

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.

$\endgroup$

Your Answer

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