Проблема Эрдёша
Системой разновесов называется совокупность натуральных чисел, из которой нельзя извлечь два различных набора с одинаковой суммой (например, числа 1, 3, 7, 20 образуют систему разновесов, а числа 1, 2, 3, 4, 5, 8 не образуют: $2+3+4=8+1$).
В 1956 году известный венгерский математик П. Эрдёш сформулировал следующую общую проблему: Найти наименьшее натуральное число $m(k)$ такое, чтобы из натуральных чисел, не превосходящих $m(k)$, можно было выделить систему разновесов из $k$ чисел.
Другая, в известном смысле обратная проблеме Эрдёша задача состоит в нахождении наибольшего количества $l(N)$ разновесов среди чисел, не превосходящих данного натурального $N$.
Несмотря на большой интерес, вызванный поставленными задачами у специалистов по теории чисел, теории кодирования и комбинаторному анализу, полностью они до сих пор не решены. Получены лишь некоторые оценки чисел $m(k)$ и $l(N)$, причём вопрос точности этих оценок остаётся открытым.
В задаче М675 («Квант», 1981, №3) мы предложили нашим читателям получить некоторые оценки, относящиеся к проблеме Эрдёша, для конкретных $k$ и $N$. Именно, мы предложили доказать, что из чисел, меньших 1000, можно выделить систему разновесов а) из 10 чисел; б) из 11 чисел; в) 14 чисел из них выбрать нельзя; г) если числа образуют систему разновесов, то сумма их обратных величин не превосходит $\dfrac52$. И, наконец, мы предложили д) из чисел, меньших 700, выбрать систему разновесов, состоящую из 11 чисел.
Оценки сверху
Некоторые грубые оценки сверху числа $m(k)$ можно получить из очень простых соображений.
В самом деле, $k$ чисел 1, 2, $\ldots$, $2^{k-1}$ образуют систему разновесов при любом натуральном $k$.
Упражнение 1. Докажите это.
Поэтому, очевидно, $m(k)\le2^{k-1}$. В частности, из чисел 1, 2, $\ldots$, 1000 выделяется система разновесов из 10 чисел 1, 2, $\ldots$, $2^{9}=512$. Это даёт решение пункта а) задачи М675.
Легко строится система разновесов и из 11 чисел, не больших 1000.
В самом деле, $k$ чисел 3, $3\cdot $, $3\cdot2^2$, $\ldots$, $3\cdot2^{k-1}$ также образуют систему разновесов. Добавим к ним два числа $3\cdot 2^{k-1}-1$ и $3\cdot2^{k-1}+1$ и докажем, что получающиеся числа также образуют систему разновесов.
Если какой-то набор из этих чисел содержит оба добавленных числа (тогда набор из оставшихся чисел их не содержит), то его сумма не меньше, чем $3\cdot2^k$, и, следовательно, больше суммы всех остальных чисел.
Если же какой-нибудь набор содержит одно добавленное число, то любой набор, его не содержащий, будет иметь сумму, дающую при делении на 3 остаток, отличный от остатка при делении на 3 суммы исходного набора.
При $k=9$ получаем систему разновесов 3, 6, 12, $\dots$, 767, 768, 769 из 11 чисел (это даёт решение пункта б)).
Итак, $m(11)\le769$. Вообще же нами получена оценка $m(k)\le3\cdot2^{k-2}+1$.
Оценка снизу
Попробуем теперь оценить число $m(k)$ снизу.
Пусть $a_1\lt a_2\lt\ldots\lt a_k$ — система разџовесов из $k$ чисел ($k\gt1$).
Очевидно, что $ka_k-1\ge a_1+a_2+\ldots+a_k$. Поскольку любые два набора из данных чисел имеют разные суммы, а общее число наборов из $k$ чисел равно $2^k-1$, получаем неравенство $a_1+a_2+\ldots+a_k\ge2^k-1$.
Упражнение 2. Убедитесь в этом.
Поэтому $ka_k\ge2^k$, т. е. $a_k\ge\dfrac{2^k}k$. В частности, для $k=14$ получим $a_{14}\ge\dfrac{2^{14}}{14}\gt1000$. Это даёт решение пункта в).
Итак, $m(k)\ge\dfrac{2^k}k$.
Теперь мы можем оценить сумму $\dfrac1{a_1}+\ldots+\dfrac1{a_k}$. Поскольку любая подсистема системы разновесов сама является системой разновесов, неравенство $a_i\ge\dfrac{2^i}i$ справедливо при любом $i$, большем 1. Отсюда
$$
\dfrac1{a_1}+\dfrac1{a_2}+\ldots+\dfrac1{a_k}\le1+\dfrac2{2^2}+\dfrac3{2^3}+\ldots+\dfrac k{2^k}.
$$
Вычислим сумму $S(k)=\dfrac2{2^2}+\ldots+\dfrac k{2^k}$. Заметим, что $2S(k)=1+\dfrac3{2^2}+\ldots+\dfrac k{2^{k-1}}$ и поэтому
$$
S(k)=2S(k)-S(k)=1+\dfrac1{2^2}+\dfrac1{2^3}+\ldots+\dfrac1{2^{k-1}}-\dfrac k{2^k}=\dfrac32-\dfrac{k+2}{2^k}\lt\dfrac32.
$$
Таким образом,
$$
\dfrac1{a_1}+\dfrac1{a_2}+\ldots+\dfrac1{a_k}\lt\dfrac52
$$
— утверждение пункта г) также доказано.
Сравнительно недавно (1977 год) американские математики Ф. Хансон, Дж. Стил и Ф. Стенджер доказали более сильное неравенство:
$$
\dfrac1{a_1^s}+\dfrac1{a_2^s}+\ldots+\dfrac1{a_k^s}\lt\dfrac{2^s}{2^s-1}
$$
для любого $s\gt0$. В частности, при $s=1$ получаем
$$
\dfrac1{a_1}+\ldots+\dfrac1{a_k}\lt2.
$$
Некоторые наблюдения
Числа 1, 2, 4, $\ldots$, 512, как мы видели, образуют систему из 10 разновесов. Посмотрим, нельзя ли, пользуясь этой системой, получить систему разновесов из 11 чисел, меньших 1000.
Рассмотрим 11 чисел: $999-0$, $999-1$, $\ldots$, $999-512$. Докажем, что это — система разновесов.
Будем в дальнейшем называть длиной набора количество чисел в этом наборе.
Прежде всего ясно, что два набора одинаковой длины имеют разные суммы (мы вычитаем из 999 нуль и числа; дающие систему разновесов).
Докажем теперь, что более длинный набор имеет бо́льшую сумму.
В самом деле, сумма шести самых маленьких чисел системы: $(999-512)+(999-256)+\ldots+(999-16)$ — больше суммы пяти самых больших из этих чисел: $999+(999-1)+(999-2)+(999-4)+(999-8)$.
Пусть теперь $a_1$, $a_2$, $\ldots$, $a_m$ и $b_1$, $b_2$, $\ldots$, $b_l$ — два набора из наших чисел, причём $m\gt l$. Если $m\gt6$, то $a_1+\ldots+a_m$, очевидно, больше $b_1+\ldots+b_l$. Если же $m\le6$, то $a_1+\ldots+a_m$ не меньше суммы $m$ наименьших чисел нашей системы, которая в свою очередь больше суммы $l$ ($l\lt m$) самых больших чисел системы (убедитесь в этом!); последняя же сумма, конечно, не меньше $b_1+\ldots+b_l$.
Итак, мы построили ещё одну систему разновесов из 11 чисел, меньших 1000.
Проанализируем проведённое доказательство.
Прежде всего заметим, что вместо числа 999 мы могли бы взять любое число $a$, для которого
$$a+(a-1)+(a-2)+(a-4)+(a-8)\lt(a-16)+\ldots+(a-512),$$
т. е. любое $a\gt512+\ldots+16-8-4-2-1=993$.
Кроме того, мы воспользовались тем, что суммы наборов одинаковой длины различны.
Попробуем обобщить наши наблюдения. Возьмём $k$ натуральных чисел $a_1\lt a_2\lt\ldots\lt a_k$, для которых суммы любых двух наборов одинаковой длины различны.
Теперь, если $k$ — чётно ($k=2l$), выберем число $a$ так, чтобы выполнялось неравенство
$$
(a-a_{2l})+\ldots+(a-a_l)\gt(a-a_{l-1})+\ldots+(a-a_1)+a,
$$
а если $k$ нечётно ($k=2l+1$) — то неравенство
$$
(a-a_{2l+1})+\ldots+(a-a_{l+1})\gt(a-a_{l-1})+\ldots+(a-a_1)+a.
$$
Так построенные числа $a$, $a-a_1$, $\ldots$, $a-a_k$ образуют систему разновесов длины $k+1$.
Упражнение 3. Докажите это утверждение.
Упражнение 4. Докажите, что из двух наборов одинаковой длины, состоящих из различных чисел построенной системы, большую сумму имеет набор, содержащий наибольшее из выбранных чисел.
Улучшенная система разновесов
Пользуясь описанным способом, мы можем строить системы разновесов любой длины $k$.
Построим сначала последовательность чисел $a_1\lt a_2\lt\ldots\lt a_n\lt\ldots$, удовлетворяющую таким соотношениям:
$$
\begin{aligned}
a_1&=0,\quad a_2=1,\\
a_{2n+1}&=(a_{n+1}+a_{n+2}+\ldots+a_{2n})-(a_1+a_2+\ldots+a_{n-1})+1,\\
a_{2n+2}&=(a_{n+1}+a_{n+2}+\ldots+a_{2n+1})-(a_1+a_2+\ldots+a_n)+1.
\end{aligned}
$$
при $n\ge1$.
Выпишем первые одиннадцать членов этой последовательности: 0, 1, 2, 4, 7, 13, 24, 46, 88, 172, 337.
Положим $a=(a_{11}+a_{10}+\ldots+a_6)-(a_5+a_4+a_3+a_2+a_1)+1=667$.
По доказанному ранее мы получаем систему разновесов из 11 чисел: 667, $667-1$, $667-2$, $\ldots$, $667-337$. Все эти числа меньше 700. Это даёт решение пункта д) задачи.
Упражнение 5. Докажите, что $m(6)=24$.
Система Конвея—Гая
Из всех систем разновесов, известных в настоящее время, на роль «рекордсмена» претендует система, построенная американскими математиками Конвеем и Гаем. В частности, для разновесов из 11 чисел у них самое большое число равно 594.
Построение, предложенное Конвеем и Гаем, состоит в следующем (см. таблицу):
$$
\def\|{\vphantom{\dfrac00}}
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
n&0&1&2&3&4&5&6&7&8&9&10&11&12\|\\\hline
x_n&0&1&2&2&3&3&3&4&4&4&4&5&5\|\\\hline
y_n&0&0&0&1&1&2&3&3&4&5&6&6&7\|\\\hline
z_n&0&1&2&4&7&13&24&44&81&161&309&594&1164\|\\\hline
\end{array}
$$
В первой строке таблицы записаны 0 и натуральные числа; во второй строке последовательность $(x_n)$, в которой всякое число $k\gt0$ встречается ровно $k$ раз; в третьей строке — последовательность $(y_n)$, полученная вычитанием чисел второй строки из чисел первой строки ($y_n=n-x_n$). Последовательность $(z_n)$ задаётся рекуррентно: $z_0=0$, $z_1=1$, $z_{n+1}=2z_n-z_{y_n}$. (Например, чтобы вычислить $z_7$, надо взять $z_6=24$, умножить его на 2 и вычесть $z_3=4$, поскольку $y_6=3$.) Последовательность $(z_n)$ записана в последней строке таблицы.
Упражнение 6. Докажите, что $x_n=(\sqrt{2n})$, где через $(x)$ обозначено ближайшее к $x$ целое число.
Конвей и Гай высказали гипотезу, что при любом $n\gt0$ числа $a_0=z_n-z_0$, $a_1=z_n-z_1$, $\ldots$, $a_{n-1}=z_n-z_{n-1}$ образуют систему разновесов, и проверили её для всех $n\le40$. (При $n=11$ получается следующая система разновесов: 594, 593, 592, 590, 587, 581, 570, 550, 510, 473, 285; как мы видим, наибольшее число здесь равно 594.)
В 1974 году индийский математик Х. Гупта доказал справедливость гипотезы Конвея—Гая и тем самым получил оценку для числа $m(k)$: $m(k)\le z_k$. Совсем недавно советский математик В. Д. Яковлев независимо получил другое доказательство.
Очень интересно было бы для какого-нибудь $n$ найти пример системы разновесов из $n$ чисел, в которой самое большое число было бы меньше $z_n$. Тем самым было бы показано, что процедура получения систем разновесов Конвея—Гая всё-таки не наилучшая.
