Докажем, что из данных чисел можно выбрать достаточно много таких пар $(a,b)$, что произведение $ab$ — квадрат целого числа; точнее: из $N$ чисел (с 9 простыми множителями) можно выбрать не менее $\dfrac{N-2^9}2$ таких пар. В нашей задаче $N=1985$, так что можно выделить не менее $\dfrac{1985-512}2$, т. е. по крайней мере 737 пар $(a,b)$. Затем к $N=737$ целым числам $\sqrt{ab}$ можно применить ещё раз то же рассуждение и получить такую пару $(\sqrt{ab},\sqrt{cd})$ — даже $\dfrac{737-512}2+\dfrac12=113$ таких пар, — что произведение $\sqrt{ab}\cdot\sqrt{cd}$ — квадрат целого числа, т. е. $abcd$ — четвёртая степень целого числа.
Осталось доказать сформулированный факт. По основной теореме арифметики каждое натуральное число однозначно представляется в виде произведения простых множителей. Произведение $ab$ двух целых чисел
$$
a=2^{\alpha_1}3^{\alpha_2}\ldots23^{\alpha_9}\quad\text{и}\quad
b=2^{\beta_1}3^{\beta_2}\ldots23^{\beta_9}
$$
будет точным квадратом в том и только том случае, если показатели $\alpha_i$ и $\beta_i$, имеют одинаковую чётность (для каждого $i$ от 1 до 9); в этом случае наборы $(\alpha_1,\alpha_2,\ldots,\alpha_9)$ и $(\beta_1,\beta_2,\ldots,\beta_9)$ показателей мы будем называть сравнимыми. Будем из $N$ наборов показателей, соответствующих $N$ данным числам (с множителями 2, 3, $\ldots$, 23), выделять одну за другой пары сравнимых наборов, до тех пор, пока это возможно. Наборов без пары останется не более $2^9$, поскольку существует всего $2^9$ попарно несравнимых наборов показателей (на каждом из 9 мест может стоять либо чётное, либо нечётное число — всего $2^9$ вариантов).
Эта задача, предложенная Монголией на последней международной олимпиаде, — частный случай следующей, видимо, очень трудной проблемы. Пусть заданы натуральные числа $\alpha$ и $m$. Для какого $N$ можно утверждать, что из $N$ любых наборов $(\alpha_1,\alpha_2,\ldots,\alpha_d)$, где $\alpha$ — целые числа, можно выбрать $m$ наборов, сумма $i$-х координат которых делится на $m$ (для каждого $i=1$, 2, $\ldots$, $d$)? Естественно, что $N$ должно быть больше $\dfrac{m-1}{2^d}$ (по крайней мере, уменьшить эту оценку нельзя: достаточно взять все наборы из нулей и единиц, каждый по $m-1$ раз). Интересно было бы доказать или опровергнуть гипотезу, что наименьшее $N=N(d,m)$, для которого верно сформулированное выше утверждение, равно $(m-1)2^d+1$, или хотя бы получить оценки для $N(d,m)$. Для $d=1$ — т. е. для целых чисел $\alpha$ — эта гипотеза доказана: $N(1,m)=2m-1$ (см. «Квант», 1971, № 7, с. 30 и № 8, с. 43). Она верна также для $m=2^k$: из факта, доказанного в решении задачи М957, эквивалентного неравенству $N(d,2m)\le2N(d,m)+2^d-1$, и очевидного неравенства $N(d,2)\le2^d+1$ вытекает, что $$
\begin{gather*}
N(d,4)\le2^d+2^{d+1}+1,\quad N(d,8)\le 2^d+2^{d+1}2^{d+2}+1,\quad\ldots,\\
N(d,2^k)\le2^d+2^{d+1}+\ldots+2^{d+k-1}+1=(2^k-1)2^d+1
\end{gather*}
$$
таким образом, $N(d,2^k)=(2^k-1)2^d+1$.
Не менее интересна (довольно близкая) проблема, предложенная нашим читателем Д. Флейшманом: в той же ситуации требуется выбрать из $N$ наборов несколько (не обязательно ровно $m$), сумма которых «делится на $m$».
