Обозначим сумму остатков от деления $2^n$ на числа 1, 2, $\ldots$, $n$ через
$S_n$. Мы усилим утверждение задачи и докажем, что при $n\gt1000$
$S_n\gt3{,}5n$. Попутно мы докажем тем же методом, что $$
S_n\gt\frac n2(\log_2n-4)
$$
при любом $n$.
Мы следуем, в основном, решению Д. Григорьева из Ленинграда. Решение основано на очень простом соображении: $2^n$ не делится
нацело ни на какое нечётное число, отличное от 1, значит, остаток от деления
$2^n$ на такое число не меньше 1. Отсюда легко вывести, что для любого
нечётного $k\gt1$ остаток от деления $2^n$ нa $2^lk$ не меньше $2^l$,
Действительно, пусть остаток от деления $2^{n-l}$ на $k$ равен $r$, т. е.
$2^{n-l}=mk+r$, где $0\le r\lt k$, тогда $2^n=m(2^lk)+2^lr$, где $0\le2^lr\gt2^lk$, т. е. остаток от деления $2^n$ на $2^lk$ равен $2^lr$, и так как $r\ne0$, то этот остаток не меньше $2^l$.
Отсюда следует, что во всяком случае
$$
\begin{align*}
S_n\ge1&{}\cdot\text{(количество не превосходящих $n$ чисел вида $2k+1$, $k\gt1$)}+{}\\
{}+2&{}\cdot\text{(количество не превосходящих $n$ чисел вида $2(2k+1)$, $k\gt1$)}+{}\\
{}+2^2&{}\cdot\text{(количество не превосходящих $n$ чисел вида $2^2(2k+1)$, $k\gt1$)}+{}\\
&{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\,{\ldots}\\
{}+2^l&{}\cdot\text{(количество не превосходящих $n$ чисел вида $2^l(2k+1)$, $k\gt1$)},\tag{*}
\end{align*}
$$
где $l$ определяется условиями $3\cdot2^l\le n$, $3\cdot2^{l+1}\gt n$ (нет
смысла брать большее $l$, так как тогда выражение в скобках будет равно
нулю).
Что можно сказать про правую часть этого неравенства?
Рассмотрим $(i+1)$-е слагаемое: $2^i(\ldots)$. Число, стоящее в скобках,
равно, очевидно, числу не превосходящих $n$ членов арифметической прогрессии
$3\cdot2^i$, $5\cdot2^i$, $7\cdot2^i$, $\ldots$, т. е. прогрессии с первым членом
$3\cdot2^i$ и разностью $2\cdot2^i$. Число таких членов не меньше
$\dfrac{n-3\cdot2^i}{2^{i+1}}$ и, значит, $(i+1)$-е слагаемое правой части
не меньше $\dfrac n2-\dfrac32\cdot2^i$. В основном, решение задачи на этом
окончено. Всё остальное — это различные преобразования правой части (*) с помощью полученных неравенств. Заменим, например, сумму в правой части (*)
первыми восемью слагаемыми. Тогда мы получим
$$
S_n\gt8\cdot\dfrac n2-\dfrac32\sum\limits_{i=0}^72^i\gt
8\cdot\dfrac n2-\dfrac32\cdot2^8=3{,}5n+\left(\dfrac n2-384\right).
$$
При $n\gt1000$ выражение в скобках положительно и, значит, мы доказали,
что $S_n\gt3{,}5n$ при $n\gt1000$. Тем самым задача М33 полностью решена.
Однако можно получить более точное неравенство. Просуммируем все члены
правой части (*); получим:
$$
S_n\gt(l+1)\dfrac n2-\dfrac32\sum\limits_{i=0}^l2^i\gt
(l+1)\dfrac n2-\dfrac{3\cdot2^{l+1}}2.
$$
Воспользовавшись неравенствами $3\cdot2^l\le n$, $3\cdot2^{l+1}\gt n$,
найдём, что $$
S_n\gt \dfrac n2\log_2\dfrac n3-n=\dfrac n2\left(\log_2\dfrac n3-2\right)\gt
\dfrac n2(\log_2n-4).
$$
Эта формула показывает, например, что если $n\gt2^{1004}$, то $S_n\gt500n$.
Задача. Сумма остатков от деления чисел
$2^{l+1}$, $\ldots$, $2^{l+L}$ на нечётное число $m\gt1$ больше, чем $\dfrac
m2\left(\dfrac L{\log_22m}-1\right)$.
С помощью этой задачи, решение которой будет приведено ниже, можно
доказать, что для бесконечного числа значений $n$ сумма $S_n$ на самом деле
гораздо больше, чем $\dfrac n2(\log_2n-4)$, т. е. можно доказать, что оценка
$S_n\gt\dfrac n2(\log_2n-4)$ очень груба (по крайней мере для бесконечного
числа значений $n$). Это и неудивительно, так как наш мeтод доказательства
не учитывал многих обстоятельств. Например, мы использовали только то, что остатки от деления $2^n$ на нечётные числа отличны от нуля, в то время как эти остатки часто бывают довольно большими. Вместе с тем, величина $S_n$ с ростом $n$ нe может расти слишком быстро, так как очевидно, что $$
S_n\le 1+2+\ldots+(n-1)=\dfrac{n(n-1)}2.
$$
Нам кажется вероятным, что справедлива такая гипотеза:
Гипотеза 1. а) При достаточно
больших $n$ верно неравенство $S_n\le\dfrac{n^2}4$;
б) существует положительное число $c\gt0$ такое, что $cn^2\le
S_n$.
Мы не умеем ни доказывать, ни опровергать эти утверждения.
Более того, мы не знаем, справедлива ли более слабая
Гипотеза 2. Существует
положительное число $c\gt0$ такое, что неравенство $cn^2\le S_n$ выполняется
при бесконечном числе значений $n$.
Если вам удастся доказать или опровергнуть одну из этих
гипотез, присылайте нам ваши рассуждения. Если они окажутся интересными, мы опубликуем их в одном из номеров журнала. В качестве слабого подтверждения
гипотезы 2 может быть доказана следующая
Теорема. Для бесконечного числа
значений $n$ выполняется неравенство$$
S_n\gt\frac{n^2}{132\log_2n}.
$$
Теорема выводится из задачи следующим образом. Рассмотрим сумму $\Sigma_k$
остатков от деления чисел $2^{k+1}$, $\ldots$, $2^n$ на число $k$. Согласно
задаче, при нечётном $k$ сумма $\Sigma_k$ достаточно велика, поэтому и число
$\Sigma_1+\Sigma_2+\ldots+\Sigma_k$ велико. Ho, как легко заметить,
$S_1+S_2+\ldots+S_n=\Sigma_1+\Sigma_2+\ldots+\Sigma_n$, поэтому сумма,
стоящая в левой части, также велика и, значит, одно из слагаемых, скажем
$S_l$, также велико. Аккуратное проведение доказательства мы предоставляем
читателю. Перейдём теперь к решению задачи.
Решение задачи. Выпишем остатки от деления чисел $2^{l+1}$, $\ldots$, $2^{l+L}$ на $m$ и будем ставить между двумя
последовательными остатками «галочку», если первый больше второго. Тогда,
во-первых, остаток, стоящий перед галочкой, больше $\dfrac m2$, во-вторых,
количество чисел между двумя последовательными галочками меньше $\log_2m$,
так как остатки между двумя галочками образуют геометрическую прогрессию со знаменателем 2 (действительно, $2^{\log_22m-1}=m\gt m-1$, а всякий остаток
не больше $m-1$). Таким образом, число промежутков между галочками больше
$\dfrac L{\log_22m}-1$ и так как в конце каждого промежутка стоит число,
большее $\dfrac m2$, то всё доказано.
