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