Задача No. 79370

Решение

а) Ответ: такая последовательность существует.

Построим последовательность (a_n), ни один из членов которой не равен сумме нескольких других, такую, что при всех n одновременно a_n ≤ n¹⁰ и a_n ≤ 100n^7/2. Сначала положим b_m = 10^{5^{m - 2}} для всех натуральных m ≥ 2, то есть b₂ = 10, b₃ = 100 000, b₄ равно единице с 25 нулями, и т. д. Последовательность (a_n) будем строить "по пачкам". Первую пачку возьмём состоящей из одного числа — единицы. В качестве m-й пачки при m ≥ 2 возьмём арифметическую прогрессию с первым членом 2b_m + 1, разностью 2b_m и числом членов, равным b_m²/2:

2b_m + 1, 4b_m + 1, ..., b_m³ + 1

Оценим сумму чисел m-й пачки

$\displaystyle {\frac{(2b_m+1)+(b_m^3+1)}{2}}$ · $\displaystyle {\frac{b_m^2}{2}}$ = $\displaystyle {\frac{b_m^5+2b_m^3+2b_m^2}{4}}$ < $\displaystyle {\frac{b_m^5}{2}}$ < b_m⁵ − b_m = b_{m + 1} − b_m.

Таким образом, сумма чисел в пачках от 1-й до m-й включительно меньше

1 + (b₃ − b₂) + ... + (b_{m + 1} − b_m) = b_{m + 1} − b₂ + 1 < b_{m + 1}.

Допустим, что некоторое число a из m-й пачки (m > 2) представимо в виде суммы некоторых других членов построенной последовательности. Так как сумма всех чисел в пачках с номерами, меньшими m, меньше b_m < 2b_m + 1 ≤ a, среди этих членов последовательности найдётся несколько чисел из m-й пачки; обозначим их c₁,..., c_k. Остальные члены нашей суммы обозначим через d₁, ..., d_l.

a = c₁ + ... + c_k + d₁ + ... + d_l.

Так как сумма первых b_m чисел m-й пачки равна

(2b_m + 1) + (4b_m + 1) + ... + (2b_m² + 1) = b_m³ + b_m² + b_m > b_m³ + 1,

то есть больше наибольшего числа m-й пачки, и, следовательно, больше a, мы получаем, что k < b_m. Обозначим r=k + (d₁ + ... + d_s)

r = k + (d₁ + ... + d_s) < b_m + (d₁ + ... + d_s) < 2b_m.

Но a − r = (c₁ + ... + c_k) − k = (c₁ - 1) + ... + (c_k − 1). Поскольку каждое число из m-й пачки при делении на 2b_m даёт в остатке 1, числа c₁ − 1, c₂ − 1, ..., c_k − 1 делятся на 2b_m, так что a − r делится на 2b_m. Так как при этом r < 2b_m, r равно остатку от деления a на 2b_m, то есть r = 1; значит, k + d₁ + ... + d_l = 1, что невозможно (при a ≠ c₁).

Отсюда заключаем, что ни один член построенной последовательности (a_n) не равен сумме нескольких других.
Проверим теперь, что a_n ≤ 100n^7/2 при любом n. При n = 1 это очевидно. Если a_n лежит во второй пачке, то a_n ≤ 1001 < 100^.2^7/2 ≤ 100n^7/2. Пусть a_n лежит в m-й пачке и m ≥ 3. Представим a_m в виде 2kb_m + 1 (1 ≤ k ≤ b_m²/2) и рассмотрим два случая.

1^o. k ≤ b_{m - 1}². Тогда

a_n ≤ 2b_{m - 1}²b_m + 1 < 3b_{m - 1}²b_m = 3b>⁷_{m - 1} = 3^.2^{7/2 .}(b_{m - 1}²/2)^7/2

Но b_{m - 1}²/2 < n, поскольку b_{m - 1}²/2 — число членов в (m − 1)-й пачке. Поэтому a_n ≤ 3^.2^{7/2 .}n^7/2 < 100n^7/2.

2^o. k > b_{m - 1}². Ясно, что номер a_n в m-й пачке не превосходит его номера в последовательности, то есть k

a_n = 2kb_m + 1 < 3kb_m = 3k(b>²_{m - 1})^5/2 < 3k^.k^5/2 ≤ 3n^7/2.

Таким образом, неравенство a_n ≤ 100n^7/2 доказано для всех n. Неравенство a_n ≤ n¹⁰ при n = 1 и n = 2 проверяется непосредственно, а при n > 2 вытекает из того, что

a_n ≤ 100n^7/2 < 3^{13/2 .}n^7/2 ≤ n^{13/2 .}n^7/2.

б) Ответ: такой последовательности не существует.

Докажем, что хотя бы один член последовательности (a_n) такой, что a_n < 100n^3/2 при всех n = 1, 2,... равен сумме нескольких других. (Конечно, число 100 здесь можно заменить любой константой; от показателя 3/2 в нашем доказательстве нужно, чтобы он был меньше ( $\sqrt{5}$ + 1)/2.) Без ограничения общности можно считать нашу последовательность возрастающей.

Рассмотрим прямоугольную таблицу с 10³⁰ строками и 10¹⁸ столбцами. Присвоим её строкам номера от 10³⁰ + 1 до 2^.10³⁰, а столбцам — номера от 1 до 10¹⁸. На пересечении n-й строки и k-го столбца напишем число c_n, k = (a₁ + a₂ + ... + a_k) + a_n). Оно не превосходит

a₁ + ... + a_10¹⁸ + a_2^.10³⁰ ≤ 100 + 100 · 2^3/2 + ... + 100 · (10¹⁸)^3/2 + 100 · (2 · 10³⁰)^3/2 <
< 100 · (10¹⁸)^3/2 · 10¹⁸ + 100 · (10³⁰)^3/2 · 2^3/2 = 10⁴⁷ + 10⁴⁷ · 2^3/2 < 4 · 10⁴⁷.

Так как в таблице выписано 10⁴⁸ чисел, каждое из которых может принимать менее 4 · 10⁴⁷ значений, какие-нибудь два из этих чисел совпадают. Пусть, например, c_{n, k} = c_{m, l}. Поскольку в n-й строке все числа различны, n ≠ m. Можно считать, что n > m (случай m > n аналогичен). Равенство c_{n, k} = c_{m, l} означает, что

(a₁ + ... + a_k) + a_n = (a₁ + ... + a_s) + a_m,

откуда k < l и a_n = (a_{k + 1} + ... + a_s) + a_m. Так как при этом s ≤ 10¹⁸ < m, получаем, что a_n представляется в виде суммы нескольких других членов последовательности.

Ответ

а) Такая последовательность существует.
б) Такой последовательности не существует.

Условие

Решение

Ответ