5
$\begingroup$

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.

$\endgroup$
1
4
$\begingroup$

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

$\endgroup$
0
4
$\begingroup$

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.