Every integer number is colored red or blue.We know that, for each finite set of consecutive integer numbers , the absolute value of the difference between the number of integers colouredof red and the number of integers colourated of blue is at most $1000$. Prove that there exists a set of $2000$ consecutive integers between which there are exactly $1000$ red numbers and 1000 numbers blue. How can i demonstrate this question?
$\begingroup$
$\endgroup$
asked Apr 3 '15 at 12:49
-
$\begingroup$ I did not really understand the first property : "each finite set $\cdots$ " if we take for example the set $S=\{1(R),2(B),3(R),\cdots, 99(R),100(B)\}$ then will be the " the difference between the number of integers coloured of red and the number of integers colourated of blue"? $\endgroup$ – Elaqqad Apr 3 '15 at 13:07
-
$\begingroup$ Yes for example if we have 999 integers colourated of red an 1001 integer colourated of blue the difference is two $\endgroup$ – Domenico Vuono Apr 3 '15 at 13:14
$\begingroup$
$\endgroup$
Let$\let\leq\leqslant\let\geq\geqslant$ $a_n=1$ if $n$ is blue and $a_n=-1$ otherwise. We are given that $$\left|a_k+a_{k+1}+\cdots+a_{k+m}\right|\leq1000$$ for all $k,m$. We want to show that there exists $k$ such that $$S_k=a_k+\cdots+a_{k+1999}=0.$$ It suffices to show that there exist $l$ and $m$ with $S_l\leq0$ and $S_m\geq0$, because then somewhere between $l$ and $m$ there has to be a $k$ with $S_k=0$ and we are done. (Note that $S_k$ is always even and $S_{k+1}-S_k=\pm\,2$.)
Suppose not.
Wlog we can assume that $S_k>0$ for all $k$. But then $$S_0+S_{2000}+S_{4000}+\cdots+S_{1000\cdot2000}>1000,$$ contradicting $$a_0+\cdots+a_{1000\cdot2000+1999}\leq1000.$$
Note:
- The proof still applies when we are only given that $$\left|a_k+a_{k+1}+\cdots+a_{k+m}\right|\leq C$$ for some $C$.
- I only needed $2002000$ consecutive integers to find our desired $2000$ consecutive integers. In general this approach will take $2000(C+1)$ integers.
answered Apr 3 '15 at 13:13
