XVI Silk Road Math Competition

Let $1\le x_1\le x_2\le \cdots \le x_{42}\le 10^6$ be the given numbers. Suppose that $x_{2k+1}{x}_{2k+2}>4x_{2k}{x}_{2k-1}$ for every $k=1,2,\dots ,20$. Multiplying all these inequalities for every $k=1,2,\dots ,20$ we obtain $x_{41}{x}_{42}>4^{20}{x}_1{x}_2\ge 4^{20}$, hence $x_{42}>2^{20}>10^6$, contradiction. Therefore, there is $k$ ($1\le k\le 20$) such that $x_{2k+2}{x}_{2k+1}\le 4x_{2k}{x}_{2k-1}$ (). Let's prove that $(x_{2k-1},x_{2k},x_{2k+1},x_{2k+2})$ satisfies the constraints. In fact, let $(a,b,c,d)$ be some permutation of these numbers. From () it follows that $4ac\ge bd$, $4bd\ge ac$. Then $$\begin{array}{rl}& 25(ab+cd)(ad+bc)-16(ac+bd{)}^2=\\ & 25(ac(b^2+d^2)+bd(a^2+c^2))-100abcd+(68abcd-16a^2{c}^2-16b^2{d}^2)=\\ & 25ac(b-d{)}^2+25bd(a-c{)}^2+4(4ac-bd)(4bd-ac)\ge 0,\end{array}$$ proved.