numbers from $1$ to $2046$

Question

We have randomly taken $21$ integers from $1$ to $2046$.

Show that we can take $a$, $b$ and $c$ from the previous $21$ integers in a way such that the following inequality holds \begin{equation} bc<2a^2<4bc \end{equation}

My Attempt:

I have found $3$ triplets of such integers, but I do not think the above inequalities hold for every triplet.

Any hints ?

Answer 1

Let the 21 numbers be $x_1<x_2<\ldots <x_{21}$.

It is not possible to have $x_{k+2}\ge 2x_k+1$ (or equivalently $x_{k+2}+1\ge 2(x_k+1)$) for all $k$ as that would lead to $2047 \ge x_{21}+1\ge 2^{10}(x_1+1)\ge 2^{11}=2048$. Thus we find $k$ such that $x_{k+2}\le 2x_k$. With $b:=x_k$, $a:=x_{k+1}$, $c:=x_{k+2}\le 2b$, we have $$ bc\le 2b^2<2a^2<2c^2\le 4bc$$ as desired.

---

The above proof suggests that the conditions are sharp (i.e., drawing only 20 numbers from $1,\ldots 2046$, or drawing 21 numbers from $1,\ldots,2047$ might not suffice to guarantee the existence of such triples. However, we see that already $x_3=3$ allows to pick $a=2, b=1,c=3$ with $bc=3<2a^2=8<4bc=12$. Hence we may assume $x_3\ge 4$ and obtain $x_{21}\ge 2^9\cdot (x_3+1)-1=2559$. We conclude that $2046$ can be replaced with $2558$ in the problem statement.

Further investigation shows that we can even go up to $3070$: If $x_3\ge 5$ we find as above that $x_{21}\ge2^9(x_3+1)-1=3071$. So we may assume $x_3=4$. If $x_2=2$, we find $x_1=1$ and have our triple; and if $x_2=3$ then $x_2,x_3,x_4$ is our triple as long as $x_4\le 10$. We conclude $x_4\ge 11$, $x_{21}>x_{20}\ge 2^8(x_4+1)-1\ge 3071$.

Answer 2

Let set $S$ be the set of integers from $1$ to $2046$, we split $S$ to $S_i$s like this:

$$S_1=\{1,2,3\}\\S_i=\{s\in\mathbb{Z}\,|\,2^{i}\le s\lt2^{i+1}\}\quad (2\le i\lt10)\\ S_{10}=\{1024,1025,\dots,2046\}$$ So we have $10$ sets in total, by Pigeonhole principle there's a set which has at least $\lceil\frac{21}{10}\rceil=3$ elements from those $21$ chosen ones.

Name these three $a,b,c$ such that $c\lt a\lt b$, then try to prove these inequalities.

Answer 3

Note that for any three positive integers $a,b,c$, if $2^k\leqslant b<a<c<2^{k+1}$ for some $k\in\mathbb{Z}_{>0}$, then $$bc<ac<a\cdot 2^{k+1}=2a\cdot 2^k\leqslant 2a\cdot a=2a^2,$$ and $$bc>ba\geqslant 2^ka=\frac{1}{2}\cdot 2^{k+1}a>\frac{1}{2}\cdot a\cdot a=\frac{1}{2}a^2.$$

Thus, $2^k\leqslant b<a<c<2^{k+1}$ for some $k\in\mathbb{Z}_{>0}\Rightarrow bc<2a^2<4bc.$

And $b=1,a=2,c=3$ also satisfies the requirement.

Note that we can divide the integers from $1$ to $2046$ into ten parts:

\begin{align*} & A_1=\{1,2,3<2^2\}\\ & A_2=\{2^2=4,5,6,7<2^3\}\\ & \dots \\ & A_{10}=\{2^{10}=1024, 1025,\dots, 2046<2^{11}\} \end{align*} If we choose $21=10\times 2+1$ integers in $[1,2046]$,we can always find three of them $x_1<x_2<x_3$ falls in the same part $A_i$. Then we can let $b=x_1,a=x_2,c=x_3$.