# Largest subset with no arithmetic progresssions

Let $$A=\{x_1,x_2,\cdots,x_n\}$$ be a set of $$n$$ distinct real numbers. Show that there exists a set $$B\subset A$$ such that $$|B|\geq\lfloor\sqrt{2n}+\frac12\rfloor$$ and no $$3$$ distinct elements of $$B$$ constitute an arithmetic progression.

I have no idea how to approach this problem, with its strange-looking formula. I've already posted it on AoPS but no reply.

• Jan 20 '18 at 17:22

This is much weaker:

Call a subset of $A$ good if it has no $3$-element arithmetic progression.

Let $X$ be a maximal good subset of $A$ and let $m=|X|$, then for every other point $x\in A\setminus X$ there is a two element subset $\{a,b\}\subseteq X$ so that $x,a$ and $b$ form a progression in some order.

Notice that each subset can form a progression with at most $3$ other points.

So $3\binom{m}{2}\geq n-m\implies 3m(m-1)\geq 2n-2m\implies 3m^2-m\geq2n\iff m\geq\frac{\sqrt{24 n+1}+1}{6}$

This is accurate estimate!

Perform a greedy algorithm. At start $$B= \emptyset$$. Now repeat: Take arbitrary element $$a\in A$$, delete it in $$A$$ and

• if it doesn't make AP in $$B$$ then put it in $$B$$ .
• if $$a$$ make AP with some $$x,y\in B$$ and
• if $$a\ne {x+y\over 2}$$ (it is not in the middle of $$x,y$$) then we refute it,
• if $$a= {x+y\over 2}$$ (it is in the middle of $$x,y$$) then we replace $$x$$ or $$y$$ with $$a$$ in $$B$$.

We finish when $$A = \emptyset$$. Now we do double counting between unordered pairs in $$B$$ and $$B^C$$. Pair $$\{x,y\}\subset B$$ connect with $$z\in B^C$$ iff $$x,y,z$$ are in AP.

Every unordered pair in $$B$$ is connected with at most $$1$$ (and not $$3$$) elements in $$B^C$$. So, if $$|B|=m$$, then we have:

$$\binom{m}{2}\geq n-m\iff m\geq\frac{\sqrt{8n+1}+1}{2}$$