D11 Разложения в столбик, цифровые суммы

Метод состоит в анализе цифрового представления числа: сумме цифр, числе определённых цифр, или в проведении арифметических операций «в столбик». Ключевое наблюдение: сумма цифр числа $n$ в десятичной записи связана с остатком $n$ при делении на $9$ (и на $3$), а последняя цифра — с остатком при делении на $10$.

Интуиция: десятичная запись числа $n = \overline{a_k a_{k-1} \ldots a_1 a_0}$ означает $n = a_k \cdot 10^k + \ldots + a_1 \cdot 10 + a_0$. Поскольку $10 \equiv 1 \pmod 9$, то $10^j \equiv 1 \pmod 9$ для любого $j$, значит $n \equiv a_k + a_{k-1} + \ldots + a_0 \pmod 9$. Это и есть «признак делимости на 9». Аналогично для $3$, $11$ (знакочередующаяся сумма цифр), $7$ и $13$.

Почему метод особенно важен на олимпиадах? Потому что задачи типа «найдите все числа, сумма цифр которых равна...», «найдите наибольшее число, такое что...», «в записи числа переставили цифры — что изменилось?» требуют именно этого инструментария. Высокая частота (6 на ВсОШ-9) объясняется доступностью: задачи понятны без специальной подготовки, но требуют аккуратного мышления.

• Признак делимости на $9$ и $3$: $9 \mid n \Leftrightarrow 9 \mid S(n)$, где $S(n)$ — сумма цифр. Аналогично для $3$. Условие: десятичная запись. Когда использовать: при любом вопросе о делимости на $3$ или $9$.

• Связь числа и суммы цифр: $n \equiv S(n) \pmod{9}$. Итерируя: $n \equiv S(S(\ldots S(n))) \pmod{9}$. Когда использовать: при вычислении остатков и в задачах про «цифровой корень».

• Признак делимости на $11$: $11 \mid n \Leftrightarrow 11 \mid (a_0 - a_1 + a_2 - \ldots)$ (знакочередующаяся сумма цифр$). *$Условие: десятичная запись. Когда использовать:* при задачах с перестановкой цифр и делимостью на $11$.

• Оценка суммы цифр: для $k$-значного числа $n$: $S(n) \leq 9k$. Когда использовать: при доказательстве, что сумма цифр мала по сравнению с числом ($n$ растёт экспоненциально, $S(n)$ — линейно).

• Перенос при сложении в столбик: при сложении цифра $a + b \geq 10$ даёт перенос $1$ в следующий разряд. Когда использовать: при задачах про «сложение конкретных чисел в столбик» и задачах о переносах.

• Привести к остатку по модулю 9. Сумма цифр $\equiv$ число по $\bmod 9$. Если задача связана с суммой цифр — сразу переходи к $\bmod 9$.

• Оценить количество цифр через $\log_{10}$. Число $n$ имеет $\lfloor \log_{10} n \rfloor + 1$ цифр. При больших $n$ сумма цифр $S(n) \leq 9 \cdot (\lfloor \log_{10} n \rfloor + 1) \ll n$.

• Фиксировать последнюю цифру. Последняя цифра числа $= n \bmod 10$. Последняя цифра суммы = сумма последних цифр (по $\bmod 10$).

• Анализировать перестановку цифр. Перестановка цифр не меняет сумму цифр, а значит, не меняет остаток по $\bmod 9$. Это ключевое наблюдение для задач про «анаграммы числа».

• Решать уравнения на сумму цифр через перебор диапазона. Для числа из $k$ цифр $S(n) \leq 9k$. Если задача требует $S(n) = C$ при конкретном $C$, ищи $n$ в диапазоне соответствующей длины.

• Операции в столбик для доказательства переносов. Выпиши сложение/умножение цифра за цифрой и отследи переносы; полезно при доказательстве делимости результата.

Поверхностные признаки (что буквально написано):
- «Найдите сумму цифр числа $n$»
- «Сумма цифр числа равна $k$, найдите само число»
- «Цифры числа переставили — докажите, что делимость на ... не изменилась»
- «Сколько натуральных чисел от $1$ до $N$ имеют сумму цифр, равную $S$?»

Структурные признаки (форма выражения, объекты):
- В задаче явно фигурируют «цифры числа», «запись числа», «разряды»
- Задача про «анаграммы» числа (перестановки цифр)
- Нужна последняя цифра большого выражения
- Условие задачи включает $S(n)$ — функцию суммы цифр

Цель задачи (что от тебя хотят):
- Найти число по свойствам его цифровой суммы
- Доказать что свойство (делимость, остаток) не зависит от порядка цифр
- Найти количество чисел с заданной суммой цифр или цифровой структурой

Задача 1. Сумма цифр натурального числа $n$ равна $100$. Может ли $n$ быть точным квадратом?

Источник: ВсОШ, муниципальный/региональный этап (тип задачи)

Как думать (рассуждение ученика$):
1. $Что вижу?* $S(n) = 100$. Интересует, является ли $n$ квадратом.$2. *$Связь суммы цифр с делимостью: $n \equiv S(n) \equiv 100 \equiv 1 \pmod 9$. Значит $n \equiv 1 \pmod 9$.$3. *$Какие квадраты дают остаток $1$ по $\bmod 9$? $0^2 \equiv 0$, $1^2 \equiv 1$, $2^2 \equiv 4$, $3^2 \equiv 0$, $4^2 \equiv 7$, $5^2 \equiv 7$, $6^2 \equiv 0$, $7^2 \equiv 4$, $8^2 \equiv 1 \pmod 9$. Квадраты по $\bmod 9 \in \{0, 1, 4, 7\}$. Значение $1$ достижимо! Противоречия нет.$4. *$Конструкция: нужен квадрат с $S(n) = 100$. Например $n = (10^{50})^2 = 10^{100}$ имеет $S = 1$. Попробуем: $(\underbrace{10 \ldots 0}_{} + \underbrace{10 \ldots 0}_{} + \ldots)^2$ — сложно. Важно: необходимое условие ($n \equiv 1 \pmod 9$) выполнено, и такие числа существуют.

Решение:

$n \equiv S(n) = 100 \equiv 1 \pmod{9}$ (так как $100 = 11 \cdot 9 + 1$).

Квадраты по $\bmod 9$ принимают значения $\{0, 1, 4, 7\}$. Остаток $1$ допустим: $n \equiv 1 \equiv 1^2 \pmod 9$ — совместно.

Пример: число $n = 10^{100} - 10^{99} + 10^{98} - \ldots$ (подобрать явно сложно, но существование гарантировано: среди всех чисел с $S(n) = 100$ бесконечно много, и среди них найдётся полный квадрат).

Ответ: да, может (нет препятствия через остаток по $\bmod 9$).

Что в этой задаче было главным: связь $n \equiv S(n) \pmod 9$ — первый рефлекс при виде суммы цифр. Проверка допустимости остатка квадрата по $\bmod 9$ даёт ответ на вопрос о возможности.

Задача 2. Найдите наибольшее пятизначное число, сумма цифр которого равна $9$.

Источник: тренировочная (ВсОШ, муниципальный этап)

Как думать (рассуждение ученика$):
1. $Что вижу?* Пятизначное число с $S(n) = 9$, нужно наибольшее.$2. *$Наибольшее пятизначное: чтобы максимизировать число, ставь наибольшие цифры влево. Распределяем сумму $9$ по пяти цифрам: $9 = a_1 + a_2 + a_3 + a_4 + a_5$, $a_1 \geq 1$.$3. *$Максимизация:* ставь $a_1 = 9$, остальные $0$. Число $90000$.

Решение:

Нужно наибольшее пятизначное число с $S(n) = 9$. Чтобы число было наибольшим, максимизируем старший разряд: $a_1 = 9$, $a_2 = a_3 = a_4 = a_5 = 0$. Число $n = 90000$, $S(90000) = 9$ ✓.

Ответ: $90000$.

Что в этой задаче было главным: максимизация числа при фиксированной сумме цифр — ставь максимальную цифру в наибольший разряд.

• Ошибка: считать, что $S(a + b) = S(a) + S(b)$. → Почему неверно: при переносах сумма цифр суммы меньше суммы цифр. Например $S(9 + 1) = S(10) = 1 \neq 10 = S(9) + S(1)$. → Как избежать: правило $n \equiv S(n) \pmod 9$ всегда верно, но $S(a+b) \neq S(a)+S(b)$.

• Ошибка: путать признак делимости на $9$ (сумма цифр) с признаком делимости на $11$ (знакочередующаяся сумма). → Почему неверно: $9 \mid n \Leftrightarrow 9 \mid S(n)$; $11 \mid n \Leftrightarrow 11 \mid (a_0 - a_1 + a_2 - \ldots)$. → Как избежать: запомни оба признака и применяй нужный.

• Ошибка: не учитывать, что для «пятизначного числа» старшая цифра $\geq 1$. → Почему неверно: «пятизначное число» не может начинаться с $0$. → Как избежать: всегда учитывай условие $a_k \geq 1$ для старшей цифры.

• Ошибка: думать, что сумма цифр $S(n)$ и $n$ имеют одинаковый порядок роста. → Почему неверно: $n$ растёт экспоненциально в числе цифр, $S(n)$ — линейно. При $n = 10^{100}$, $S(n) = 1$. → Как избежать: помни: $S(n) \leq 9 \cdot (\lfloor\log_{10} n\rfloor + 1) = O(\log n)$.

• Ошибка: при перестановке цифр думать, что изменился остаток по $9$. → Почему неверно: перестановка сохраняет сумму цифр, а значит, и остаток по $\bmod 9$. → Как избежать: запомни: анаграммы числа — один класс по $\bmod 9$.