|
|
 |
Условие
а) Существует ли последовательность натуральных чисел a1, a2, a3, ..., обладающая следующим свойством: ни один член последовательности не равен сумме нескольких других и an ≤ n10 при любом n?
б) Тот же вопрос, если an ≤ n при любом n.
Решение
а) Построим последовательность (an), в которой ни один из членов не равен сумме нескольких других и при всех n одновременно an ≤ n10 и
an ≤ 100n3,5. Сначала положим bm = 105m–2 для всех натуральных m ≥ 2, то есть b2 = 10, b3 = 105, b4 = 1025 и т.д.
Последовательность (an) будем строить "по пачкам".
Первую пачку возьмём состоящей из одного числа – единицы. В качестве m-й пачки при m ≥ 2 возьмём арифметическую прогрессию с первым членом 2bm + 1, разностью 2bm и числом членов, равным
Оценим сумму чисел m-й пачки:
Таким образом, сумма чисел в пачках от 1-й до m-й включительно меньше 1 + (b3 − b2) + ... + (bm + 1 − bm) = bm+1 − b2 + 1 < bm+1.
Допустим, что некоторое число a из m-й пачки (m > 2) представимо в виде суммы некоторых других членов построенной последовательности. Так как сумма всех чисел в пачках с номерами, меньшими m, меньше bm < 2bm + 1 ≤ a, среди этих членов последовательности найдётся несколько чисел из m-й пачки; обозначим их c1, ..., ck. Остальные члены нашей суммы обозначим через d1, ..., dl, a = c1 + ... + ck + d1 + ... + dl.
Так как сумма первых bm чисел m-й пачки равна
то есть больше наибольшего числа m-й пачки, и, следовательно, больше a, мы получаем, что k > bm. Обозначим r = k + (d1 + ... + ds) < bm + (d1 + ... + ds) < 2bm.
Но a − r = (c1 + ... + ck) − k = (c1 − 1) + ... + (ck − 1). Поскольку каждое число из m-й пачки при делении на 2bm даёт в остатке 1, числа c1 − 1, c2 − 1, ..., ck − 1 делятся на 2bm, так что a − r делится на 2bm. Так как при этом r < 2bm, то r равно остатку от деления a на 2bm, то есть r = 1; значит,
k + d1 + ... + dl = 1, что невозможно (при a ≠ c1).
Отсюда заключаем, что ни один член построенной последовательности (an) не равен сумме нескольких других.
Проверим теперь, что an ≤ 100n3,5. При n = 1 это очевидно. Если an лежит во второй пачке, то an ≤ 1001 < 100·23,5 ≤ 100n3,5.
Пусть an лежит в m-й пачке и m ≥ 3. Представим am в виде и рассмотрим два случая.
1) Тогда
Но поскольку
– число членов в (m−1)-й пачке. Поэтому an ≤ 3·23,5·n3,5 < 100n3,5.
2) Ясно, что номер an в m-й пачке не превосходит его номера в последовательности, то есть k ≤ n Значит,
Таким образом, неравенство an ≤ 100n3,5 доказано для всех n. Неравенство an ≤ n10 при n = 1 и n = 2 проверяется непосредственно, а при n > 2 вытекает из того, что an ≤ 100n3,5 < 36,5·n3,5 ≤ n6,5·n3,5.
б) Докажем, что хотя бы один член последовательности (an), в которой an < 100n1,5 при всех n = 1, 2, ..., равен сумме нескольких других. Без ограничения общности можно считать нашу последовательность возрастающей.
Рассмотрим прямоугольную таблицу с 1030 строками и 1018 столбцами. Присвоим её строкам номера от 1030 + 1 до 2·1030, а столбцам – номера от 1 до 1018. На пересечении n-й строки и k-го столбца напишем число cnk = (a1 + a2 + ... + ak) + an. Оно не превосходит
a1 + ... + a1018 + a2·1030 ≤ 100 + 100·21,5 + ... + 100·(1018)1,5 + 100·(2·1030)1,5 < 100·(1018)1,5·1018 + 100·(1030)1,5·21,5 = 1047 + 1047·21,5 < 4·1047.
Так как в таблице выписано 1048 чисел, каждое из которых может принимать менее 4·1047 значений, какие-нибудь два из этих чисел совпадают. Пусть, например, cnk = cml. Поскольку в n-й строке все числа различны, n ≠ m. Можно считать, что n > m (случай m > n аналогичен). Равенство cnk = cml означает, что (a1 + ... + ak) + an = (a1 + ... + al) + am, откуда k < l и an = (ak+1 + ... + al) + am. Так как при этом l ≤ 1018 < m, получаем, что an представляется в виде суммы нескольких других членов последовательности.
Ответ
а) Существует; б) не существует.
