Почему при переходе от 9 к 10 сумма цифр падает на 8, а не на 9?

Девятка на конце превращается в ноль, и сумма теряет 9. Но слева появляется новая единица, и сумма получает 1. Итого 9 − 9 + 1 = 1, то есть на 8 меньше прежнего. То же и при переходе от 99 к 100: 18 − 18 + 1 = 1.

Почему остаток при делении на 3 не сбивается при переходе через разряд?

При переходе мы вычитаем девятки: 9, 18 и другие кратные девяти. Все они делятся на 3, поэтому остаток от вычитания не меняется. Меняет его только прибавленная единица, которая сдвигает остаток на следующий: 0 → 1 → 2 → 0.

Откуда в конце берётся умножение на 2?

Это не правило делимости, а число подходящих строк в каждой группе. В каждой тройке строк подходят вторая и третья, то есть две. Групп 33, поэтому 33 · 2 = 66, и отдельно добавляется 101-я строка.

Сто одна строка без огромных чисел: делимость на 3 и повторение

Числа 1, 12, 123 проверить нетрудно. А если строк сто одна, и в последней подряд выписаны все числа от 1 до 101? Ниже — как считать не сами огромные записи, а величину поменьше, и почему найденный порядок не оборвётся.

видеоразбор · 2 мин 59 с

Тот же разбор за три минуты

Суммы цифр, переход через разряд и группы по три строки появляются пошагово. В статье то же решение с таблицами, доказательством и задачей для самостоятельной пробы.

Ролик лежит на нашем сервере: без сторонних проигрывателей и рекламы. Звук включается в плеере.

Задача

В первую строчку записали число 1. Во вторую — число 12. Дальше в строчку с номером $k$ записывали число, которое получается приписыванием к предыдущей строчке числа $k$ . Например, в двенадцатой строчке будет записано число 123456789101112. Всего выписали 101 строчку. Сколько из этих чисел делятся на 3?

Задача школьного этапа ВсОШ — Всероссийской олимпиады школьников — на платформе «Сириус»: математика, 8 класс, 2024 год, группа 1, задание 4, вариант 1. Условие и авторство принадлежат организаторам; ниже — наш учебный разбор.

Важное уточнение: в каждой строке стоит одно число. Приписать 10 — значит дописать справа две цифры, 1 и 0, а не прибавить десять к предыдущему числу.

Попробуйте до чтения разбора: выпишите первые шесть строк и отметьте, какие числа делятся на 3. Как продолжать проверку, не деля каждую запись в столбик?

Догадка

Выпишу первые несколько строк, увижу закономерность «нет, да, да» и просто продолжу её до сто первой строки.

Первая половина верна: закономерность действительно такая. Но продолжить её «на глазок» нельзя. Впереди переход от 9 к 10 и от 99 к 100, где к записи добавляется сразу две или три цифры. Вдруг именно там порядок и собьётся? Проверим.

Рассуждение

Считаем не число, а сумму его цифр. Число делится на 3 тогда и только тогда, когда на 3 делится сумма его цифр. Для 1234 сумма равна 10 — не делится; для 12345 сумма 15 — делится.

Старые цифры при переходе к следующей строке никуда не деваются, добавляются только новые. Значит, сумму можно наращивать:

Строка	Число	Сумма цифр	Делится на 3
1	1	1	нет
2	12	3	да
3	123	6	да
4	1234	10	нет
5	12345	15	да
6	123456	21	да

Порядок «нет, да, да» виден. Пока это наблюдение, а не доказательство.

Что происходит на переходе через разряд. В строке, оканчивающейся на …789, сумма цифр равна 45. В следующей строке конец уже …78910: добавились цифры 1 и 0, поэтому новая сумма равна $45 + 1 + 0 = 46$ , а вовсе не 55. Дальше приписываем 11 и получаем 48, приписываем 12 и получаем 51. Снова «нет, да, да».

Чтобы понять почему, посмотрим отдельно на сумму цифр нового номера, а не всей строки. У номера 8 она равна 8, у 9 равна 9, а у 10 всего 1. Девятка на конце превратилась в ноль, и сумма потеряла 9; слева появилась единица, и сумма получила 1:

$9 - 9 + 1 = 1.$

То же самое на сотне: у 99 сумма цифр 18, у 100 она равна 1, потому что $18 - 18 + 1 = 1$ . Обе девятки стали нулями, и добавилась одна новая единица.

Доказательство

Шаг 1. Переход через разряд не портит остаток. Без перехода сумма цифр номера растёт ровно на 1. При переходе каждая девятка на конце превращается в ноль, поэтому дополнительно вычитается 9 за каждую такую девятку. Но 9, 18 и любое другое кратное девяти делится на 3, значит, остаток при делении на 3 от этого вычитания не меняется. Меняет его только прибавленная единица: она сдвигает остаток на следующий, $0 \to 1 \to 2 \to 0$ .

Шаг 2. Остатки новых номеров повторяются. Из первого шага следует, что остатки сумм цифр подряд идущих номеров идут циклом

$1,\; 2,\; 0,\; 1,\; 2,\; 0,\; \ldots$

и переход к 10 или к 100 этот цикл не разрывает.

Шаг 3. Отсюда порядок в строках. После третьей строки сумма равна 6 и делится на 3. Дальше добавка с остатком 1 портит делимость; добавка с остатком 2 добавляет недостающее и возвращает её; добавка с остатком 0 сохраняет. На числах это ровно $6 \to 10 \to 15 \to 21$ . Следующая тройка добавок имеет те же остатки, поэтому повторяет те же шаги.

Значит, в каждой группе из трёх подряд идущих строк подходят вторая и третья: строки 1, 2, 3, потом 4, 5, 6 и так далее.

Шаг 4. Считаем. В первых 99 строках ровно $99 : 3 = 33$ группы, в каждой два подходящих числа:

$33 \cdot 2 = 66.$

Двойка здесь не признак делимости, а количество подходящих строк в группе. Остаются две строки. После 99-й сумма делится на 3. Приписываем 100 и добавляем к сумме цифр 1 — сотая строка не подходит. Приписываем 101 и добавляем ещё 2, а $1 + 2 = 3$ — сто первая подходит.

$66 + 1 = 67.$

Ответ: 67 чисел.

Проверим, что учтены все строки: $33 \cdot 3 + 2 = 101$ . Группы не пересекаются, внутри каждой разобраны все три позиции, обе оставшиеся строки рассмотрены отдельно.

Что и требовалось — понять

Прибавить сам номер вместо суммы его цифр: после строки с суммой 45 получить $45 + 10 = 55$ . Здесь перепутаны приписывание номера и сложение чисел.

Исправление: приписанный номер 10 приносит две цифры, 1 и 0, поэтому сумма цифр становится 46.

Если огромная запись растёт по понятному правилу, а спрашивают только про делимость, следите за величиной поменьше: здесь это сумма цифр, а затем её остаток. Найдите повторение и обязательно объясните, почему оно не оборвётся, — иначе это догадка, а не решение. После доказательства считайте целые группы, а хвост списка разбирайте отдельно.

Признак суммы цифр работает для деления на 3 и на 9, но не для любого делителя: 12 делится на 4, а сумма его цифр 3 — нет. И при другом порядке приписывания повторение придётся проверять заново.

Попробуйте сами

Авторская задача на тот же приём, не олимпиадная. По тому же правилу выписали только первые 14 строк. Сколько из этих чисел делятся на 3?

Подсказка

Сколько групп по три строки помещается в первых двенадцати? Какие позиции в следующей группе занимают строки 13 и 14?

Показать ответ

Четыре полные группы дают $4 \cdot 2 = 8$ подходящих чисел. Строка 13 стоит первой в новой группе и не подходит, строка 14 — второй и подходит. Итого 9.

Проверка: суммы цифр строк 12, 13 и 14 равны 51, 55 и 60. Подходящие строки целиком: 2, 3, 5, 6, 8, 9, 11, 12, 14.

Следующий шаг

Эту же задачу можно решить иначе, вообще не считая суммы цифр: одно начало, два решения. Там длинная запись заменяется суммой подряд идущих чисел, а дальше развилка: превратить сумму в произведение или доказать период через разность.

Ещё одна задача, где вместо перебора считают по правилу: шестизначные числа из единиц и двоек. Там все варианты считают по дереву, а потом вычитают неподходящие.