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.
 A: 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}$$
A: 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}$
