Сумма цифр строки и сумма 1 + 2 + … + n — это одно и то же?

Нет. У двенадцатой строки сумма цифр равна 51, а 1 + 2 + … + 12 равно 78. Числа разные, но их разность равна 27 и делится на 3, поэтому остаток при делении на 3 у них общий. Именно остаток нам и нужен.

Почему удвоение суммы не портит делимость на 3?

Умножение на 2 добавляет в разложение числа только двойку. Тройка от этого не появится и не исчезнет: 15 = 3 · 5 и 30 = 2 · 3 · 5 делятся на 3, а 14 = 2 · 7 и 28 = 2 · 2 · 7 не делятся. Работает это потому, что 2 на 3 не делится.

Какой из двух путей правильнее?

Оба полные и оба засчитываются. Первый короче: период вообще не нужен, делимость видна из произведения. Второй объясняет, откуда берётся порядок «нет, да, да», который замечают почти все, — и превращает наблюдение в доказательство.

Почему нет строки с номером 102?

Число 102 появляется не как номер строки, а как n + 1 для последней, сто первой строки. Строк ровно 101, и последняя из них подходит.

Сто одна строка: одно начало, два решения

Начало у обоих решений одно: длинная запись заменяется короткой суммой. А дальше пути расходятся. Один превращает сумму в произведение, и делимость видна сразу. Другой доказывает, почему повторяется порядок «нет, да, да», который замечают почти все.

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

Два ролика — по одному на каждый путь

Начало у них общее: приписывание раскладывается на умножение, лишнее кратное трём уходит. Дальше каждый идёт своей дорогой. В статье оба решения с выкладками и задачами для самостоятельной пробы.

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

Первый путь: сумма становится произведением. 2 мин 25 с.

Второй путь: доказанный период и группы по три. 2 мин 35 с.

Задача

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

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

Ту же задачу мы разбирали ещё и через сумму цифр. Там начало другое: следим за суммой цифр записи, а не за суммой номеров.

Догадка

В двенадцатой строке приписаны числа от 1 до 12. Значит, сумма её цифр равна $1 + 2 + \ldots + 12 = 78$ .

Заманчиво и почти верно. Но сумма цифр двенадцатой строки равна 51, а не 78: число 10 приносит цифры 1 и 0, то есть единицу, а не десять. Зато разность $78 - 51 = 27$ делится на 3. Именно из-за этого догадкой можно пользоваться — если аккуратно объяснить, почему разность всегда кратна трём.

Рассуждение: общее начало

Приписывание — это умножение и сложение. Приписать к числу 123 цифру 4 значит получить $123 \cdot 10 + 4$ . Разложим десятку на $9 + 1$ :

$1234 = (123 + 4) + 9 \cdot 123.$

Слагаемое $9 \cdot 123$ делится на 3. Убрать его — значит не изменить остаток. Поэтому 1234 и сумма $123 + 4$ делятся на 3 одновременно, хотя сами числа разные.

Двузначные и трёхзначные номера ничего не ломают. Пусть $A$ — число в предыдущей строке. Приписать двузначное $k$ — это $A \cdot 100 + k$ , и здесь работает та же разборка:

$A \cdot 100 + k = (A + k) + 99 A, \qquad A \cdot 1000 + k = (A + k) + 999 A.$

Числа 99 и 999 делятся на 3, значит, и вычитаемые слагаемые тоже. Номера в задаче не длиннее трёх цифр, так что этих двух случаев хватает на все 101 строку.

Что остаётся. Повторяя разборку до самого начала, мы каждый раз выбрасываем кратное трём. Остаётся сумма всех приписанных номеров:

$S_n = 1 + 2 + \ldots + n.$

Число в строке $n$ и эта сумма дают одинаковый остаток при делении на 3. Дальше работаем только с ней — и вот здесь пути расходятся.

Доказательство, путь первый: сумма становится произведением

Шаг 1. Складываем сумму саму с собой. Запишем её дважды, второй раз в обратном порядке, и сложим по столбцам:

\begin{aligned} S_n &= 1 + 2 + \ldots + n, \\ S_n &= n + (n-1) + \ldots + 1. \end{aligned}

В каждом столбце получается $n + 1$ , столбцов ровно $n$ . Значит, $2 S_n = n (n + 1)$ .

Шаг 2. Удвоение не влияет на делимость на 3. Умножение на 2 добавляет в разложение числа только двойку. Тройка от этого не появится и не исчезнет, потому что 2 на 3 не делится. Поэтому $S_n$ делится на 3 тогда и только тогда, когда на 3 делится $n(n+1)$ .

Шаг 3. Произведение делится на 3, когда делится один из множителей. Число 3 простое, значит, оно обязано войти в разложение $n$ или в разложение $n + 1$ . Других возможностей нет.

Шаг 4. Считаем оба случая. Номера, которые сами делятся на 3, — это 3, 6, 9, …, 99, их $99 : 3 = 33$ . Во втором случае на 3 делится $n + 1$ , то есть $n + 1$ пробегает 3, 6, 9, …, 102, а сами номера равны 2, 5, 8, …, 101, их $102 : 3 = 34$ .

Число 102 — это не строка, а $n + 1$ для последней, сто первой строки. Такой строки в задаче нет, и она не считается.

Шаг 5. Случаи не пересекаются. Если бы $n$ и $n + 1$ оба делились на 3, то и их разность делилась бы на 3. Но разность равна 1. Значит, ни один номер не посчитан дважды:

$33 + 34 = 67.$

Обратите внимание: период «нет, да, да» на этом пути не понадобился вовсе.

Доказательство, путь второй: доказанный период и группы

Шаг 1. Что видно на первых суммах. Выпишем $S_1, \ldots, S_6$ : это 1, 3, 6, 10, 15, 21. Делимость на 3: нет, да, да, нет, да, да. Период в три строки заметен, но пока это наблюдение, а не довод.

Шаг 2. Сравниваем строки через три шага. Во второй строке проверяем $S_2 = 1 + 2$ . В пятой — $S_5 = (1 + 2) + 3 + 4 + 5$ . Разница между ними это сумма трёх подряд идущих чисел.

Шаг 3. Три соседних числа выравниваются. Возьмём $3 + 4 + 5$ и передадим единицу от пятёрки к тройке. Сумма не изменилась: одно слагаемое выросло на 1, другое на столько же уменьшилось. Получилось $4 + 4 + 4 = 3 \cdot 4$ , и делимость на три видна без вычислений.

С любыми тремя подряд идущими числами выйдет так же. Для строки с номером $n$ добавляются $n+1$ , $n+2$ и $n+3$ , а после передачи единицы все три становятся равны $n+2$ :

$S_{n+3} - S_n = (n+1) + (n+2) + (n+3) = 3(n+2).$

Шаг 4. Отсюда период. Прибавление кратного трём не меняет остаток. Значит, строки $n$ и $n+3$ либо обе подходят, либо обе не подходят — и никакой переход через разряд этому помешать не может, потому что в выкладке нет ни одной цифры записи.

Первая строка не подходит, поэтому не подходят 4-я, 7-я и дальше через три. Вторая подходит, поэтому подходят 5-я, 8-я и дальше. Третья подходит — и с ней 6-я, 9-я и дальше. Теперь порядок «нет, да, да» доказан.

Шаг 5. Считаем группы. Разобьём первые 99 строк на непересекающиеся тройки: (1, 2, 3), затем (4, 5, 6) и так до (97, 98, 99). Групп ровно $99 : 3 = 33$ , и в каждой подходят вторая и третья строки:

$33 \cdot 2 = 66.$

Двойка здесь — количество подходящих строк в группе, а не какое-то новое правило делимости. Остались строки 100 и 101: первая стоит в новой тройке первой и не подходит, вторая — второй и подходит:

$66 + 1 = 67.$

Ответ: 67 чисел. Оба пути дают его независимо друг от друга.

Проверим край списка. Для сотой строки $S_{100} = 100 \cdot 101 : 2 = 5050$ , сумма цифр 10 — не делится. Для сто первой $S_{101} = 101 \cdot 102 : 2 = 5151$ , сумма цифр 12 — делится. И счёт строк сходится: $33 \cdot 3 + 2 = 101$ .

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

На первом пути: решить, что раз сумму удвоили, то результат надо разделить на 2, и делимость от этого не пострадает. Деление вообще не обязано сохранять делимость: 6 делится на 3, а после деления на 3 остаётся 2. Исправление: делить ничего не нужно, достаточно один раз объяснить, почему множитель 2 не добавляет и не убирает тройку.

На втором пути: написать «дальше повторяется» и сразу перейти к подсчёту групп. Ответ получится верный, но проверяющий вправе спросить, откуда известно, что период не оборвётся на сотне. Исправление: показать, что разность $S_{n+3} - S_n$ равна $3(n+2)$ и потому кратна трём при любом $n$ .

Когда числа строятся приписыванием, запишите это действие через умножение на 10, 100 или 1000. Если спрашивают про делимость на 3, лишнюю часть, кратную трём, можно выбросить сразу — от этого остаток не изменится. Это общее начало обоих решений, и оно же самая ценная часть.

Дальше выбирайте по вкусу. Если после чистки осталась сумма подряд идущих чисел, сложите её с собой в обратном порядке: получится произведение, у которого делимость видна без всякой периодичности. А если период всё же хочется использовать, посчитайте разность величин, отстоящих на три шага: когда она кратна трём, повторение доказано сразу для всех случаев.

Приём с передачей единицы работает шире. Сумма трёх подряд идущих чисел всегда делится на 3, потому что их можно выровнять. Сумма пяти подряд идущих делится на 5 по той же причине. А вот сумма четырёх подряд идущих на 4 не делится: у чётного количества слагаемых нет середины.

Переносить решение на другой делитель без проверки нельзя. Числа 12 и $1 + 2$ дают разные остатки при делении на 7, и весь ход рассуждения там разваливается на первом же шаге.

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

Две авторские задачи на тот же приём, не олимпиадные. Решите каждую своим путём и сравните, какой оказался быстрее.

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

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

Путём первым: номера, кратные трём, — 3, 6, …, 48, их 16. Номера, где на 3 делится $n + 1$ , — это $n + 1 = 3, 6, \ldots, 51$ , их 17. Всего $16 + 17 = 33$ .

Путём вторым: первые 48 строк дают 16 полных троек по два подходящих числа, это 32. Из строк 49 и 50 подходит только пятидесятая. Снова 33.

Вторая. А теперь только первые 17 строк.

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

Первые 15 строк дают 5 полных групп по два подходящих числа: $5 \cdot 2 = 10$ . Строка 16 стоит первой в новой тройке и не подходит, строка 17 — второй и подходит. Итого 11.

Проверка перечислением: 2, 3, 5, 6, 8, 9, 11, 12, 14, 15, 17.

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

Третий взгляд на ту же задачу, с совсем другим началом: сто одна строка через сумму цифр. Там длинная запись заменяется не суммой номеров, а суммой цифр, и период доказывается через цикл остатков 1, 2, 0.

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