For any positive integer $n$, define $$c_n=\min_{(z_1,z_2,...,z_n)\in\{-1,1\}^n} |z_1\cdot 1^{2018} + z_2\cdot 2^{2018} + ... + z_n\cdot n^{2018}|.$$Is the sequence $(c_n)_{n\in\mathbb{Z}^+}$ bounded?
Problem
Source: Serbia TST 2018 P6
Tags: algebra, combinatorics
MarkBcc168
29.05.2018 14:00
This problem is killed by the following lemma (which I forgot the source.)
Lemma : There exists partitions of $\{0,1,2,...,2^n-1\}$ to $A, B$ such that for each $k=0,1,2,...,n-1$, we have
$$\sum_{a\in A} a^k = \sum_{b\in B} b^k$$(here $0^0=1$.)
seoneo
29.05.2018 14:28
The name of the above lemma is Prouhet–Tarry–Escott problem.
Rickyminer
06.06.2018 07:33
Sorry, but how does this lemma help?
nikolapavlovic
06.06.2018 09:50
MarkBcc168 wrote:
This problem is killed by the following lemma (which I forgot the source.)
Lemma : There exists partitions of $\{0,1,2,...,2^n-1\}$ to $A, B$ such that for each $k=0,1,2,...,n-1$, we have
$$\sum_{a\in A} a^k = \sum_{b\in B} b^k$$(here $0^0=1$.)
It even holds over any basis,it's an old problem from Kvant which i posted and if i remember correctly Darij posted a solution. Amazingly on the actual TST i hadn't even thought about it.
MarkBcc168
06.06.2018 10:47
Basically, it tells that for any group of $2^{2019}$ consecutive numbers, there exists a way to assign $z_i$ so that the resulting sum is zero. Thus the sequence is bounded by $\max\{a_1,a_2,...,a_{2^{2019} }\}$.
rcorreaa
09.11.2019 19:53
MarkBcc168 wrote:
This problem is killed by the following lemma (which I forgot the source.)
Lemma : There exists partitions of $\{0,1,2,...,2^n-1\}$ to $A, B$ such that for each $k=0,1,2,...,n-1$, we have
$$\sum_{a\in A} a^k = \sum_{b\in B} b^k$$(here $0^0=1$.)
How can we prove this lemma?
Gomes17
11.08.2020 21:51
We generalize this problem. Namely, we prove that $$c_n=\min_{(z_1,z_2,...,z_n)\in\{-1,1\}^n} |z_1\cdot P(1) + z_2\cdot P(2) + ... + z_n\cdot P(n)|.$$ is bounded for any (integer) polynomial $P$. The proof goes by induction on the degree. The constant polynomial case is immediate (alternating signs). Consider the polynomial $Q(x)=P(x+1)-P(x)$, which has degree $\deg P -1$. For $n$ even, take $-z_1=z_2=y_1 , -z_3=z_4=y_2 ,...$ then we have $$z_1\cdot P(1) + z_2\cdot P(2) + ... + z_n\cdot P(n) = y_1 \cdot Q(1) + y_2 \cdot Q(3) +... + y_{\frac{n}{2}} \cdot Q(n-1)$$ In this case, we may simply apply our inductive hypothesis to the polynomial $R(x)=Q(2x-1)$, which again has a degree at most $\deg P -1$. To the case $n$ odd, we start by $-z_2 = z_3 =y_1 , -z_4=z_5=y_2,...$. In this case, $$z_1\cdot P(1) + z_2\cdot P(2) + ... + z_n\cdot P(n) = (z_1 \cdot P(1)) +(y_1 Q(2) + y_2 Q(4) +...+y_{\frac{n-1}{2}} Q(n-1))$$ So, by applying our result to $H(x)=Q(2x)$ and using triangle inequality, we again get our desired result . Therefore the bound $B_P \le \max (|P(1)|+ B_H, B_R)$ works and we are done (where $B_S$ is the bound of polynomial $S$).
chirita.andrei
08.10.2021 19:25
The answer is yes. For a positive integer $n$, let $ S_n=1^{2018}+2^{2018}+...+n^{2018} $. Consider the following greedy algorithm: At each step we choose the largest number from $\{1^{2018};2^{2018};...;n^{2018}\}$ such that the sum of the chosen numbers remains smaller than $\frac{S_n}{2}$ (we do not choose a number more than one time). To each chosen number we assign $-$ and to all other numbers we assign $+$. We claim that this difference is bounded above.
Since $ f(X)=X^{2018}+(X-1)^{2018}-(X+1)^{2018} $ is a monic polynomial, there is a fixed positive integer $C$ such that for every integer $m\ge C$ we have $f(m)>0$ i.e. $ (m+1)^{2018}<m^{2018}+(m-1)^{2018} $.
We will now prove the following main claim:
Claim. If $n$ is large enough, then at least one of $C^{2018}$ and $(C-1)^{2018}$ is not chosen.
Proof: Assume the contrary. Notice that from the way the algorithm is defined, if for some integer $a\ge C$ both $a^{2018}$ and $(a-1)^{2018}$ are chosen, then $(a+1)^{2018}$ must be chosen too. By repeatedly applying this observation we get that each of $ (C-1)^{2018},C^{2018},...,n^{2018} $ must be chosen, so $$ \frac{S_n}{2}<1^{2018}+2^{2018}+...+(C-2)^{2018}$$which is obviously false if $n$ is large enough.
Then if $n$ is large enough, the sum of the chosen numbers is at least $ \frac{S_n}{2}-C^{2018} $ and hence $c_n\le2C^{ 2018}$. Therefore $c_n$ is bounded.