Олимпиада имени Леонарда Эйлера 2024-2025 учебный год, I тур заключительного этапа

Среди всех остатков, которые дают степени 2 при делении на нечётное число $m$, большее 1, оказалось ровно $k$ чисел, больших $m/2$. Пусть натуральное число $n$ таково, что $2^n-1$ делится на $m$. Докажите, что если число $\dfrac{2^n-1}{m}$ представлено в виде суммы различных целочисленных степеней двойки, то количество слагаемых в такой сумме делится на $k$. ( А. Голованов )

Комментарий/решение

Поразительно, просто и со вкусом! Достаточно заметить, что $[\frac{2^{x+1}}{m}]=2[\frac{2^{x}}{m}]+1 \Leftrightarrow 2^x\pmod m > m/2$

**Лемма о количестве единиц**

Количество слагаемых в сумме различных степеней двойки равно количеству единиц в двоичной записи числа $X = \frac{2^n - 1}{m}$.

1. Рассмотрим деление «уголком» числа $(2^n - 1)$ на нечетное число $m$ в двоичной системе счисления. Единица в частном записывается на каждом шаге $i$, где текущий остаток $r_i$ удовлетворяет условию:

$$r_i > \frac{m}{2}$$

2. Последовательность остатков степеней двойки по модулю $m$ является периодичной. Пусть длина минимального периода равна $d$. По условию, внутри одного периода ровно $k$ остатков больше, чем $\frac{m}{2}$.

3. Так как по условию $(2^n - 1)$ делится на $m$, то показатель $n$ должен быть кратен периоду $d$. Пусть $n = d \cdot t$.

4. Это означает, что при процессе деления мы проходим полный цикл остатков ровно $t$ раз. В каждом таком цикле мы получаем ровно $k$ единиц в частном.

5. Итоговое количество единиц в двоичной записи числа $X$ будет равно:

$$S = k \cdot t$$

Так как $t$ — целое число, полученное количество единиц $S$ очевидно делится на $k$.