Largest subset with no arithmetic progresssions

Question

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.

Answer 1

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}$$

Answer 2

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}$