Suppose that every positve integer has been given one of the colors red, blue,arbitrarily. Prove that there exists an infinite sequence of positive integers $ a_{1} < a_{2} < a_{3} < \cdots < a_{n} < \cdots,$ such that inifinite sequence of positive integers $ a_{1},\frac {a_{1} + a_{2}}{2},a_{2},\frac {a_{2} + a_{3}}{2},a_{3},\frac {a_{3} + a_{4}}{2},\cdots$ has the same color.
Problem
Source:
Tags: search, arithmetic sequence, combinatorics proposed, combinatorics, Ramsey Theory
Fedor Petrov
04.04.2008 23:32
Start from $ a_1=1$ (let it be blue) and define as many $ a_i$'s as is possible. If we have defined $ a_k$, but may not define $ a_{k+1}$, then for any positive integer $ y$ at least one of numbers $ a_k+y$, $ a_k+2y$ is red, else we may define $ a_{k+1}=a_k+2y$. Note that there is some odd red $ b_1>a_k$ (else the statement follows immediately). Start from $ b_1$, define red $ b_2$ and so on in such a manner that $ b_i$ are red and odd and $ (b_i+b_{i+1})/2$ are all red. If we may not proceed, that some $ b_m$ is defined and $ b_{m+1}$ may not be defined, so for each $ z>0$ at least one of numbers $ b_m+z$, $ b_m+2z$ is blue, else define $ b_{m+1}=b_m+2z$. Next, assume that some $ X>b_m$ is blue, then $ 2X-b_m$ must be red, then $ (2X-b_m+a_k)/2=X-(b_m-a_k)/2$ is also blue. So, for $ T=(b_m-a_k)/2$ we have the following: if $ X>b_m$ is blue, then $ X-T$ is also blue. So, if $ Y>b_m-T$ is red, then $ Y+T$ is also red. So, we get an arithmetic progression of red numbers.
mychrom
05.04.2008 09:24
Isn't this just like this Kvant problem? : http://www.mathlinks.ro/Forum/viewtopic.php?search_id=341826811&t=6581 I guess that this is a pre-test for the hard Chinese tests, isn't it?
gauravpatil
16.04.2008 20:18
Fedor Petrov wrote: Next, assume that some $ X > b_m$ is blue, then $ 2X - b_m$ must be red, then $ (2X - b_m + a_k)/2 = X - (b_m - a_k)/2$ is also blue. So, for $ T = (b_m - a_k)/2$ we have the following: if $ X > b_m$ is blue, then $ X - T$ is also blue. So, if $ Y > b_m - T$ is red, then $ Y + T$ is also red. So, we get an arithmetic progression of red numbers. could you elaborate?
Fedor Petrov
16.04.2008 21:08
gauravpatil wrote: Fedor Petrov wrote: Next, assume that some $ X > b_m$ is blue, then $ 2X - b_m$ must be red, then $ (2X - b_m + a_k)/2 = X - (b_m - a_k)/2$ is also blue. So, for $ T = (b_m - a_k)/2$ we have the following: if $ X > b_m$ is blue, then $ X - T$ is also blue. So, if $ Y > b_m - T$ is red, then $ Y + T$ is also red. So, we get an arithmetic progression of red numbers. could you elaborate? $ Y$ is red, then $ Y+T$ is red, then $ Y+2T$ is red ans so on.
MariusBocanu
25.05.2014 10:32
Fedor Petrov wrote: Start from $ a_1=1$ (let it be blue) and define as many $ a_i$'s as is possible. If we have defined $ a_k$, but may not define $ a_{k+1}$, then for any positive integer $ y$ at least one of numbers $ a_k+y$, $ a_k+2y$ is red, else we may define $ a_{k+1}=a_k+2y$. Note that there is some odd red $ b_1>a_k$ (else the statement follows immediately). Start from $ b_1$, define red $ b_2$ and so on in such a manner that $ b_i$ are red and odd and $ (b_i+b_{i+1})/2$ are all red. If we may not proceed, that some $ b_m$ is defined and $ b_{m+1}$ may not be defined, so for each $ z>0$ at least one of numbers $ b_m+z$, $ b_m+2z$ is blue, else define $ b_{m+1}=b_m+2z$. Next, assume that some $ X>b_m$ is blue, then $ 2X-b_m$ must be red, then $ (2X-b_m+a_k)/2=X-(b_m-a_k)/2$ is also blue. So, for $ T=(b_m-a_k)/2$ we have the following: if $ X>b_m$ is blue, then $ X-T$ is also blue. So, if $ Y>b_m-T$ is red, then $ Y+T$ is also red. So, we get an arithmetic progression of red numbers. Just some benign typos: Next, assume that some $ X>b_m$ is red, then $ 2X-b_m$ must be blue, then $ (2X-b_m+a_k)/2=X-(b_m-a_k)/2$ is also red. So, for $ T=(b_m-a_k)/2$ we have the following: if $ X>b_m$ is red, then $ X-T$ is also red. So, if $ Y>b_m-T$ is blue, then $ Y+T$ is also blue. So, we get an arithmetic progression of blue numbers.
somebodyyouusedtoknow
03.02.2021 14:48
I'm using a do it first patch later approach, however it seems to work, and the idea seems to be very basic. Am I missing something here? Please check. EDIT: IT'S WRONG. It shows that you can always produce a red or blue term consecutively, which is useless.
Consider the case if we have finitely many positive integers that are coloured red. Then there exists a largest positive integer $k$ that is coloured red. Taking $a_1 = k + 1$, $a_2 = k + 3$, and $a_n = k + 2n + 1$, we are done, the colour of all the chosen integers are blue. For the opposite colour, the same logic applies. Hence, assume that there are infinitely many positive integers coloured red, and infinitely many positive integers coloured blue.
Without loss of generality, take $a_1$ to be the smallest positive integer coloured blue. Now use the following algorithm:
Since $a_1$ is blue, pick the next smallest blue number as $\frac{a_1 + a_2}{2}$, so $a_2$ is determined. If $a_2$ is blue, repeat the process and we are done. Otherwise, call it $b_1$ instead, so we know that $b_1$ is red. Do this procedure for every sequential term $a_k$.
Now, if after a finite amount of steps $\frac{a_1 + a_2}{2}$ leads to $a_2$ being blue, we repeat the algorithm to find $a_3, a_4, \dots$ so we have infinitely many terms.
However, if after an infinite amount of steps it always leads to a red positive integer, then we will have $b_1, b_2, b_3, \dots$ be an infinite sequence. Considering $$\frac{a_1 + b_1}{2} < \frac{b_1 + b_2}{2} < \frac{a_2 + b_1}{2}$$because $b_1 \geq a_1 + 2$, we know that $\frac{b_1 + b_2}{2}$ is a red number, otherwise $b_1 + b_2$ is odd. If this is the case, then take $\frac{b_1 + b_2 - 1}{2}$, and we know this is a red number since $$\frac{a_1 + b_1}{2} < \frac{b_1 + b_2 - 1}{2} < \frac{a_1 + b_2}{2}$$so we can repeat this whole algorithm an indefinite amount of times, generating our desired sequence. $\square$
CANBANKAN
06.06.2022 00:14
Suppose all red sequences of the form $a_1, \frac{a_1+a_2}{2} \cdots, \frac{a_{k-1}+a_k}{2}, a_k$ where $a_1$ is odd satisfies $k\le k_r$, and define $k_b$ similarly. Furthermore, suppose there is a sequence $a_1, \cdots, a_{k_r}=A$ with all red terms and $b_1,\cdots, b_{k_b}=B$ with all blue terms. WLOG $A<B$. We know $A,B$ are odd. If all sufficiently large terms are blue, we are clearly done. Otherwise, say $x$ is red. Since $A,x,2x-A$ cannot be all red or we can add $a_{k_r+1}=2x-A$, $2x-A$ is blue. Similarly, $B,x+\frac{B-A}{2}, 2x-A$ can't be all blue, so $x+\frac{B-A}{2}$ is red. Repeating the argument shows $x+\frac{B-A}{2}k$ is red for all $k\in \mathbb{N}$, and there is clearly a red sequence from these terms.