Олимпиада имени Леонарда Эйлера 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 = (2^n - 1) / m.

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

​Последовательность остатков степеней двойки по модулю m периодична. Пусть длина периода равна d. По условию, в одном периоде ровно k остатков больше m/2.

​Т.к 2^n - 1 делится на m, то n кратно периоду d (пусть n = d×t). Это значит, что при делении мы проходим полный цикл остатков t раз. В каждом цикле мы получаем k единиц. Итоговое количество единиц равно k×t что очевидно делится на k.