3
$\begingroup$

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?

$\endgroup$
  • $\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
2
$\begingroup$

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

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.