Задача
NT-B2-M11-P017 Блоки и нижняя оценка суммы цифр
Пусть \(k\ge1\). Разбейте десятичную запись положительного числа \(M\) справа налево на блоки по \(k\) цифр и обозначьте через \(T(M)\) сумму этих блоков как обычных чисел. Докажите, что \(M\equiv T(M)\pmod{10^k-1}\). Затем докажите: если \(10^k-1\mid M\), то сумма цифр числа \(M\) не меньше \(9k\).
Первую часть даёт \(10^k\equiv1\). Для второй части повторяйте операцию \(M\mapsto T(M)\).
Если \(M=B_0+B_1 10^k+B_2 10^{2k}+\cdots+B_s10^{sk}\), где \(B_i\) — блоки, то по модулю \(10^k-1\) каждая степень \(10^{ik}\) сравнима с \(1\). Поэтому \(M\equiv B_0+B_1+\cdots+B_s=T(M)\pmod{10^k-1}\).
Кроме того, сумма цифр \(T(M)\) не больше суммы цифр \(M\): при сложении блоков переносы могут только уменьшить сумму цифр. Если \(M\ge10^k\), то \(T(M)
Сильная задача: она выглядит как техника записи, но фактически использует спуск по числу.