|
|
 |
Условие
Имеется натуральное число n > 1970. Возьмём остатки от деления числа 2n на 2, 3, 4, ..., n. Доказать, что сумма этих остатков больше 2n.
Решение
Обозначим сумму остатков от деления 2n на числа 1, 2, ..., n через Sn. Мы докажем, что Sn > 3,5n при n > 1000.
2n не делится нацело ни на какое нечётное число, отличное от 1, значит, остаток от деления 2n на такое число не меньше 1. Отсюда легко вывести, что для любого нечётного k > 1 остаток от деления 2n на 2lk не меньше 2l.
Отсюда следует, что Sn ≥ n0 + 2n1 + 22n3 + ... + 2mnm, где ni – количество не превосходящих n чисел вида 2i(2k + 1), k > 1, а m определяется условиями
3·2m ≤ n < 3·2m+1 (нет смысла брать большее m, так как тогда выражение в скобке будет равно нулю).
Рассмотрим (i+1)-e слагаемое 2ini. Число ni равно числу не превосходящих n членов арифметической прогрессии 3·2i, 5·2i, 7·2i, .... Число таких членов не меньше , и, значит, это слагаемое не меньше n/2 – 3·2i–1.
Заменив сумму в правой части первыми восемью слагаемыми, получим
Sn > 8·n/2 – 3(2–1 + 1 + 2 + 2² + ... + 26) > 4n − 3·27 = 3,5n + (n/2 – 384).
При n > 1000 выражение в скобке положительно, то есть Sn > 3,5n.
Замечания
Утверждение можно еще усилить. Связанные с этим результаты и гипотезы обсуждаются в решениях Задачника "Кванта".
