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

$m>1$ тақ сан үшін, 2-нің дәрежелерін $m$-ге бөлгенде пайда болған барлық қалдықтардың ішінде $m/2$ санынан артық болатын қалдықтардың саны $k$-ға тең. Сондай-ақ, натурал $n$ саны үшін $2^n-1$ саны $m$-ге бөлінеді. Егер $\frac{2^n-1}{m}$ саны 2-нің әртүрлі бүтін дәрежелерінің қосындысына тең болса, онда қосылғыштар саны $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$.