Choose a set S consisting of $\frac{n+1}{2}$ numbers from the first $n$ natural numbers($1,2,3,...,n$) ($n\geq 2017$, $n$ is odd). Prove that there must be three numbers in S which are a 3-term arithmetic progression.
I am thinking of using recursion but I find the condition $n \geq 2017$ quite weird. Some smaller cases like $n=7$ or $n=9$ is not true (1,2,4,5) (1,2,6,7,9).
$\endgroup$ 22 Answers
$\begingroup$Write $x$ for an element fo $S$ and $o$ for a non-element. Then any (infinite) sequence of $x$'s and $o$'s can be obtained by concatenating the following building blocks:
$$o, xo, xxoo, xxoxooo, \color{red}xxo\color{red}xoo\color{red}x, x\color{red}xo\color{red}xo\color{red}x, xxoxxoooo, \color{red}xxox\color{red}xooo\color{red}x, x\color{red}xox\color{red}xoo\color{red}x, \color{red}xxo\color{red}xxo\color{red}x, xxo\color{red}{xxx}, \color{red}{xxx}$$as can be read off the following tree:
If we drop those leading to an arithmetc progression (cf. read markings) we are only left with
$$A_1= o, A_2=xo, A_3=xxoo, A_4=xxoxooo, A_5=xxoxxoooo.$$
If we use these to write down the pattern corresonding to $S$, we may produce up to four extra $o$'s. By possibly appending $A_1$, we end up with $n+4$ symbols, the last four being $o$. If $n_i$ is the number of occurences of block $A_i$, we obtain the folowing equations:$$ n_1+2n_2+4n_3+7n_4+9n_5=n+4$$$$ n_2+2n_3+3n_4+4n_5=|S|$$We conclude $$ 2|S|=n+4-n_1-n_4-n_5.$$In other words, we want to show $$\tag{!}n_1+n_4+n_5\ge 4.$$For how long a sequence can we work with only $A_2$ and $A_3$? All sequences of three blocks $A_2$ or $A_3$ lead to arithmetic progressions:
- $A_2A_2A_2=\color{red}xo\color{red}xo\color{red}xo$
- $A_2A_2A_3=\color{red}xo\color{red}xo\color{red}xxoo$
- $A_3A_3A_2=\color{red}xxoo\color{red}xxoo\color{red}xo$
- $A_3A_3A_3=\color{red}xxoo\color{red}xxoo\color{red}xxoo$
- $A_2A_3A_2=\color{red}xox\color{red}xoo\color{red}xo$
- $A_2A_3A_3=\color{red}xox\color{red}xoo\color{red}xxoo$
- $A_3A_2A_2= x\color{red}xoo\color{red}xox\color{red}o$
- $A_3A_2A_3= x\color{red}xoo\color{red}xox\color{red}xoo$
We conclude that out of three consecutive blocks, at most two are $A_2$ or $A_3$. Then $$n_2+n_3\le \left\lceil\frac{n_1+n_2+n_3+n_4+n_5}{3}\right\rceil $$or$$2(n_2+n_3)\le n_1+n_4+n_5+2.$$Now if $n_1+n_4+n_5\le 3$, this gives us $n_2+n_3\le 2$ and so $$ n=n_1+2n_2+4n_3+7n_4+9n_5-4\le 4(n_2+n_3)+9(n_1+n_4+n_5)-4\le 31.$$Hence for any $n>31$, we have $(!)$ and thererfore $$ |S|\le\frac n2.$$
$\endgroup$ 1 $\begingroup$An answer from a reputable source.
In 1936 Erdős and Turán [ET] for a natural number $n$ defined $r(n)$ as the largest size of a subset of $\{1,\dots, n\}$ without three-term arithmetic progressions. Bounds from $r(n)$ are well-studied, see this thread. Then your question is to show that $r(2n+1)\le n$ if $n\ge 1008$. Already the first theorem from [ET] stating that $r(2n)\le n$ if $n\ge 8$ provides almost the required bound. The needed improvement follows from obvious Inequality (3), stating $r(m+n)\le r(m)+r(n)$ and the equality $r(17)=8$, proved on the next page. It follows that $r(2n+1)\le n$ if $n\ge 25$. In fact, the values of $r(n)$ presented at the same page show that $r(2n+1)\le n$ if $n\ge 17$.
References
[ET] Paul Erdős, Paul Turán. On some sequences of integers, J. London Math. Soc., 11:4, (1936), 261–264. MR1574918, Zentralblatt JFM 62.1126.01.
$\endgroup$ 2
