Let $a_1,a_2,...$ be a sequence of non-negative integers such that for any $m,n$ \[ \sum_{i=1}^{2m} a_{in} \leq m.\] Show that there exist $k,d$ such that \[ \sum_{i=1}^{2k} a_{id} = k-2014.\]
Problem
Source: China Mathematical Olympiad 2015 Q6
Tags: combinatorics, algebra
21.12.2014 12:00
You most likely forgot the condition that $a_j$ must be non-negative; otherwise take all of them equal to $-2014$, and the claim is false.
21.12.2014 12:39
Oops, you're right. $a_i$ must be non-negative. Edit: The problem can be reduced to the result stated in : https://www.dpmms.cam.ac.uk/~ardm/erdoschu.pdf
12.03.2015 05:30
Who can post solution of problem for me.thank (sorry for my bad english)
09.04.2015 15:26
Consider $b_n := a_n -1/2$. Thus, we have: \[ \sum_{i=1}^{2m} b_{id} \leq 0\] and should prove, there exist $k,d$ with: \[ \sum_{i=1}^{2k} b_{id} = -2014\] Since $a_n \geq 0$, it follows $b_n$ is either $1/2$ or $-1/2$. Just to be more readable, let's write $b(n)$ instead $b_n$. When $k$ increases by one, $\sum_{i=1}^{2k} b(id)$ increases by: $0,1$, or $-1$. Hence, it's enough to prove, $\sum_{i=1}^{2k} b(id)$ is not bounded below. Suppose on the contrary, it is bounded. If $b(d)=1/2$ then $b(2d)$ must be $-1/2$. Suppose there exist infinitely many $d$ with $b(d)=-1/2$ and $b(2d)=-1/2$. Consider two finite sequences: $b(1),b(2),\dots, b(n)$ and $b(2),b(4),\dots,b(2n)$. In each of them, the number of $1/2$'s and $-1/2$'s is approximately the same, that is, the discrepancy is bounded by a constant. But to each positive $b(i)$ corresponds a negative $b(2i)$ and also there are infinitely many negative $b(i)$ for which $b(2i)$ is also negative. It follows that the difference between the number of negative terms in the sequence $b(2),b(4),\dots,b(2n)$ and the positive ones could be made as big as we want, a contradiction. It means from some index $N$ on, it holds: \[b(2n)= - b(n)\,,\, \forall n\geq N \,\,\,\,\,\,\,(*)\] Using this fact, we get \[ \sum_{i=1}^{2m} b(id) = 0\,,\, \forall m,d\,,d\geq N \,\,\,\,\,\,\, (**)\] Let fix $d \geq N$ with $b(d)=1/2$. Using (*) and (**), as done in the given link, we consecutively get: $b(2d)=-1/2,\, b(4d)=1/2,\, b(8d)=-1/2,\, b(3d)=-1/2,\, b(6d)=1/2, $ $b(12d)=-1/2,\, b(5d)=-1/2,\, b(10d)=1/2,\, b(7d)=1/2,\, b(9d)=-1/2$. Consider now $b(3d)+b(6d)+b(9d)+b(12d)$. It should be $0$, but it's $-1/2+1/2-1/2-1/2=-1$, a contradiction. Thus, $\sum_{i=1}^{2k} b(id)$ is not bounded below.
11.04.2015 16:38
I don't understand why $ b_{n} $ is $ \frac{1}{2} $ or $ -\frac{1}{2} $ . Edit:Sorry. I was stupid
30.10.2016 23:04
Statement: $ \forall l \exists d,k \sum_{i=1}^{2k} a_{id} = k-l\ $ Induction: The statement is true for $l=0;1$. Suppose $ \sum_{i=1}^{2K} a_{iD} = K-l\ $ We can clearly see $a_i=0;1$ By increasing $k$ by 1, the sum increases by -1;0;1, therefore, we only have to prove that $ \exists M \sum_{i=1}^{2K+2M} a_{iD} = K-l-b\ $ This means that the added sum has more 0-s than 1-s. $M$ can be arbitrarily large, so using the fact that at least one of $a_i$ and $a_{in}$ is 0, we can find such $M$.
28.01.2017 17:49
<dgrozev> wrote: \[b(2n)= - b(n)\,,\, \forall n\geq N \,\,\,\,\,\,\,(*)\]Using this fact, we get \[ \sum_{i=1}^{2m} b(id) = 0\,,\, \forall m,d\,,d\geq N \,\,\,\,\,\,\, (**)\] I don't think so WHY?
29.01.2017 11:30
Because if we assume $\sum_{i=1}^{2m} b(id)<0 $, it would follow $ \sum_{i=1}^{2m} b(i(2d))=- \sum_{i=1}^{2m} b(id) >0 $, a contrsdiction.
29.01.2017 14:31
Ohhhhhhh That's why!!