Олимпиада имени Леонарда Эйлера 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$