Silk Road Math Competition

Let $1 \leq x_1 \leq x_2 \leq \dots \leq x_{42} \leq 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_1x_2 \geq 4^{20}$, hence $x_{42} > 2^{20} > 10^6$, contradiction. Therefore, there is $k$ ($1 \leq k \leq 20$) such that $x_{2k+2}x_{2k+1} \leq 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 \geq bd$, $4bd \geq ac$. Then
$$\begin{aligned} & 25(ab + cd)(ad + bc) - 16(ac + bd)^2 = \\ & \quad 25(ac(b^2 + d^2) + bd(a^2 + c^2)) - 100abcd + (68abcd - 16a^2c^2 - 16b^2d^2) = \\ & \quad 25ac(b-d)^2 + 25bd(a-c)^2 + 4(4ac-bd)(4bd-ac) \geq 0, \end{aligned}$$
proved.