Системы разновесов

34

Г. Гуревич

Системы разновесов

Проблема Эрдема

Системой разновесов называется совокупность натуральных чисел, из которого нельзя извлечь два различных набора с одинаковой суммой (например, числа 1, 3, 7, 20 образуют систему разновесов, а числа 1, 2, 3, 4, 5, 8 не образуют: 2+3+4=8+1).

В 1956 году известный венгерский математик П. Эрдем сформировал следующую проблему: Найти наименьшее натуральное число m(k) такое, чтобы из натуральных чисел, не превысodiaщих m(k), можно было выделить систему разновесов из k чисел.

Другая, в известном смысле образная проблeme Эрдема задача состоит в нахождении наиболее колисества l(N) разновесов среди чисел, не превысodiaщих данного натурального N.

Несмотря на большой интерес, вызванный поставленными задачими у специалистов по теории чисел, теории кодирования и комбинаторному анализу, полностью они до сих пор не решены. Получены лишь некоторые оценки чисел m(k) и l(N), причем вопрос точно эти оценок остается открытым.

В задаче М675 («Кваант», 1981, № 3) мы предложили нашим читателем получить некоторые оценки, относится к проблeme Эрдема, для конкретных k и N. Именено, мы предложили доказать, что из чисел, меньших 1000, можно выделить систему разновесов a) из 10 чисел; б) из 11 чисел; с) из 14 чисел из них выбрать нельзя; е) если числа образуют систему разновесов, то сумма их образных величины не превысодит 5/2. И, наконец, мы предложили д) из чисел, меньших 700, выбрать систему разновесов, состоящую из 11 чисел.

Оценки сверху

Некоторые грубые оценки сверху числа m(k) можно получить из очень простых соображений.

В самом деле, k чисел 1, 2, …, 2^{k-1} образуют системы разновесов при любом натуральном k.

Упражнение 1. Докажите это.

Поэтому, оценindo, m(k) ≤ 2^{k-1}. В частности, из чисел 1, 2, …, 1000 выделяется система разновесов из 10 чисел 1, 2, …, 2^9 = 512. Это дает решение пункта a) задачи М675.

Легко строится система разновесов и из 11 чисел, не большех 1000.

В самом деле, k чисел 3, 3·2, 3·2^2, …, 3·2^{k-1} также образуют системы разновесов.

Совв. Добавим к ним два числа 3·2^{k-1} - 1 и 3·2^{k-1} + 1 и докажем, что получащие числа также образуют системы разновесов.

Если какой-то набор из этих чисел содержит оба добавленных числа (тогда набор из оставшихся чисел их не содержит), то его сумма не меньше, чем 3·2^k, и, следовательно, больше суммы всех остальных чисел.

Если же какой-нибудь набор содержит одно добавленное число, то любой набор, его не содержащий, будет иметь сумму, дающий при делении на 3 остаток, отличный от остатка при делении на 3 суммы исходного набора.

При k=9 получаем систему разновесов 3, 6, 12, …, 767, 768, 769 из 11 чисел (это дает решение пункта 6)).

Итак, m(11) ≤ 769. Вообще же нами получена оценка m(k) ≤ 3·2^{k-2} + 1.

Оценка сизу

Попробуем теперь оценить число m(k) сизу. Пусть a₁ < a₂ < … < aₖ — система разновесов из k чисел (k>1).

Очевидно, что ka_k - 1 ≥ a₁ + a₂ + … + aₖ. Поскольку любые два набора из данных чисел имеют разные суммы, а общее число набора из k чисел равно 2^k - 1, получаем неравенство a₁ + a₂ + … + aₖ ≥ 2^k - 1.

Упражнение 2. Убедитесь в этом.

Поэтому ka_k ≥ 2^k, то есть a_k ≥ 2^k/k. В частности, для k=14 получим a₁₄ ≥ 2^14/14 > 1000. Это дает решение пункта b).

Итак, m(k) ≥ 2^k/k.

Теперь мы можем оценить сумму $\frac{1}{a_1} + ... + \frac{1}{a_k}$. Поскольку любая система разновесов сама является системой разновесов, неравенство a_i ≥ $\frac{2^i}{i}$ справедливо при любом i, большем 1. Отсюда

$$\frac{1}{a_1} + \frac{1}{a_2} + ... + \frac{1}{a_k} \leq 1 + \frac{2}{2^2} + \frac{3}{2^3} + ... + \frac{k}{2^k}.$$

Вычислим сумму S(k) = $\frac{2}{2^2} + ... + \frac{k}{2^{k-1}}$ и поэтому,

$$S(k) = 2S(k) - S(k) = 1 + \frac{1}{2^2} + \frac{1}{2^3} + ... + \frac{1}{2^{k-1}} - \frac{k}{2^k} = \frac{3}{2} - \frac{k+2}{2^k} < \frac{3}{2}.$$

Таким образом,

$$\frac{1}{a_1} + \frac{1}{a_2} + ... + \frac{1}{a_k} < \frac{5}{2},$$

— утверждение пункта г) также доказано.

Сравнительно недавно (1977 год) американские математики Ф. Хансон, Дж. Стил и Ф. Степджер доказали более сильное неравенство:

$$\frac{1}{a_1^2} + \frac{1}{a_2^2} + ... + \frac{1}{a_k^2} < \frac{2^s}{2^{s-1}}$$

для любого s>0. В частности, при s=1 по-

35

Лучаем

$$\frac{1}{a_1} + \dots + \frac{1}{a_k} < 2.$$

Некоторые наблюдения

Числа 1, 2, 4, …, 512, как мы видели, образуют систему из 10 разновесов. Посмотрим, нельзя ли, пользоваться этой системой, получить систему разновесов из 11 чисел, меньших 1000.

Рассмотрим 11 чисел: 999—0, 999—1, …, 999—512. Докажем, что это — система разновесов.

Будем в дальнейшем назвать дииной набора количественного чисел в этом наборе.

Преждем всего ясно, что два набора одинаковой длины имеют разные суммы (мы вычитаем из 999 нуль и числа; дающие системы разновесов).

Докажем теперь, что более длинный набор имеет большеную сумму.

В самом деле, сумма шести самых маленьких чисел системы: (999—512) + (999—256) + … + (999—16) — больше суммы пятей самых больших из этих чисел: 999 + (999—1) + (999—2) + (999—4) + (999—8).

Пусть теперь $a_1, a_2, ..., a_m$ и $b_1, b_2, ..., b_l$ — два набора из наших чисел, причем $m > l$. Если $m > 6$, то $a_1 + ... + a_m$ очень много, больше $b_1 + ... + b_l$. Если же $m \leq 6$, то $a_1 + ... + a_m$ не меньше суммы $m$ наименьших чисел нашей системы, которая в свою очередь больше суммы $l$ ($l < m$) самых больших чисел системы (убедитесь в этом!); последняя же сумма, конечно, не меньше $b_1 + ... + b_l$.

Итак, мы построили еще одну систему разновесов из 11 чисел, меньших 1000.

Проанализируем проведенное доказательство.

Преждем всего заметим, что вместе числа 999 мы могли бы взять любое число $a$, для которого $a + (a-1) + (a-2) + (a-4) + (a-8) < (a-16) + ... + (a-512)$, то есть любое $a > 512 + ... + 16 - 8 - 4 - 2 - 1 = 993$.

Кроме того, мы воспользовались тем, что суммы наборов одинаковой длины различны.

Попробуем обобщить наши наблюдения. Возьмем $k$ натуральных чисел $a_1 < a_2 < ... < a_k$, для которых суммы любых двух наборов одинаковой длины различны.

Теперь, если $k$ — четно ($k = 2l$), выберем число $a$ так, чтобы выполялось неравенство $(a - a_{2l}) + ... + (a - a_l) > (a - a_{l-1}) + ... + (a - a_1) + a$, а если $k$ нечетно ($k = 2l+1$) — то неравенство $(a - a_{2l+1}) + ... + (a - a_{l+1}) > (a - a_{l-1}) + ... + (a - a_1) + a$.

Так построенные числа $a, a - a_1, ..., a - a_k$ образуют систему разновесов длины $k+1$. Упражнение 3.

3. Докажите это утверждение.

4. Докажите, что из двух наборов одинаковой длины, состоящих из различных чисел построенной системы, большешую сумму имеет набор, содержащий наиболее низкую сумму чисел.

Улучшенная система разновесов

Пользоваться описанным способом, мы можем строить системы разновесов любой длины $k$.

Построим сначала последовательность чисел $a_1 < a_2 < ... < a_n < ...$, удовлетворяющую таким соотношением:

$$a_1 = 0, a_2 = 1,$$

$$a_{2n+1} = (a_{n+1} + a_{n+2} + ... + a_{2n}) - (a_1 + a_2 + ... + a_{n-1}) + 1,$$

$$a_{2n+2} = (a_{n+1} + a_{n+2} + ... + a_{2n+1}) - (a_1 + a_2 + ... + a_n) + 1$$

при $n \geq 1$.

Выпишем первые одинаковые членов этой последовательности: 0, 1, 2, 4, 7, 13, 24, 46, 88, 172, 337.

Положим $a = (a_{11} + a_{10} + ... + a_6) - (a_5 + a_4 + a_3 + a_2 + a_1) + 1 = 667$.

По доказанному ранее мы получаем систему разновесов из 11 чисел: 667, 667—1, 667—2, …, 667—337. Все эти числа меньше 700. Это дает решение пункта д) задачи Упражнения 5. Докажите, что $m(6) = 24$.

Система Конверя — Гая

Из всех систем разновесов, известных в настоящие время, на роль «рекордсмена» претензует система, построенная американским математиками Конверя и Гая. В частности, для разновесов из 11 чисел у них самое большое число равно 594.

Построение, предложенное Конверя и Гая, состоит в следующем (см. таблицу):

| $n$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— | :— |
| $x_n$ | 0 | 1 | 2 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 5 | 5 | 5 |
| $y_n$ | 0 | 0 | 0 | 1 | 1 | 2 | 3 | 3 | 4 | 5 | 6 | 6 | 7 |
| $z_n$ | 0 | 1 | 2 | 4 | 7 | 13 | 24 | 44 | 81 | 161 | 309 | 594 | 1161 |

В первой строке таблицы записаны 0 и натуральные числа; во второй строке — последовательность $(x_n)$, в которой всякое число $k > 0$ встречается равно $k$ раз; в третьей строке — последовательность $(y_n)$, полученная вычитанием второй строки из чисел первого строки $(y_n = n - x_n)$. Последовательность $(z_n)$ задается рекуррентно: $z_0 = 0$, $z_1 = 1$, $z_{n+1} = 2z_n - z_{n-1}$. (Например, чтобы вычислить $z_7$, надо взять $z_6 = 24$, умножить его на 2 и вычесть $z_3 = 4$, поскольку $y_6 = 3$.) Последовательность $(z_n)$ записана в последней строке таблицы. Упражнение 6. Докажите, что $x_n = (\sqrt{2n})$, где через $(x)$ обозначено ближайшее к $x$ целое число.

Конверя и Гая высказали гипотезу, что при любом $n > 0$ числа $a_0 = z_n - z_0$, $a_1 = z_n - z_1$, …, $a_{n-1} = z_n - z_{n-1}$ образуют системы разновесов, и проверили ее для всех $n \leq 40$. (При $n = 11$ получается следующее система разновесов: 594, 593, 592, 590, 587, 581, 570, 550, 510, 473, 285; как мы видим, наиболее число здесь равно 594.).

В 1974 году индиский математик Х. Гупта доказал справедливость гипотезы Конверя — Гая и тем самым получили оценку для числа $m(k)$: $m(k) \leq z_k$. Совсем недавно советский математик В. Д. Яковелев не назвисимо получил другой доказательство.

Очень интересно было для каждого $n$ найти пример системы разновесов из $n$ чисел, в котором самое большее число было бы показано, что процедура получения системы разновесов Конверя — Гая все-tаки не наилучшая.