ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 66602
Тема:    [ Делимость чисел. Общие свойства ]
Сложность: 3+
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Найдите наименьшее натуральное число $N>9$, которое не делится на 7, но если вместо любой его цифры поставить семерку, то получится число, которое делится на 7.

Решение

Пусть наименьшее подходящее число имеет вид $\overline{a_1a_2\ldots a_n}$. Из условия следует, что среди его цифр нет 0 и 7. Если в числе есть цифры 8 или 9, то их можно заменить на 1 или 2 соответственно и получить меньшее число с тем же свойством. Таким образом, искомое число состоит из цифр от 1 до 6.

Рассмотрим соседние цифры $a_k$ и $a_{k+1}$. По условию числа с замененными семеркой цифрами $\overline{a_1a_2\ldots7a_{k+1}\ldots a_n}$ и $\overline{a_1a_2\ldots a_{k}7\ldots a_n}$ делятся на 7, следовательно, их разность также кратна 7, то есть $10a_k \equiv a_{k+1} \pmod 7$ для любого $k$. Значит, запись числа может быть устроена только следующим образом: за 1 следует 3, за 3 следует 2 (поскольку цифры 9 в числе нет) и так далее (см. рисунок).

По условию исходное число, у которого вместо последней цифры стоит 7, делится на 7. Следовательно, исходное число без последней цифры $\overline{a_1a_2a_3\ldots a_{n-1}}$ делится на 7. Используя несколько раз сравнение $10a_k \equiv a_{k+1} \pmod 7$, получаем: $$\overline{a_1a_2\ldots a_{n-1}} = a_1 10^{n-2} + a_2 10^{n-3}+a_310^{n-4} +\ldots+ a_{n-1} \equiv $$ $$ \equiv 10a_1\cdot10^{n-3} + a_2 10^{n-3}+a_310^{n-4}+\ldots+ a_{n-1}\equiv $$ $$ \equiv 2 a_2 10^{n-3}+a_310^{n-4} \ldots+a_{n-1} \equiv \ldots \equiv (n-1)a_{n-1} \pmod 7.$$ Поскольку $a_{n-1}$ не делится на 7, заключаем, что $n-1$ делится на 7, поэтому наименьшее возможное $n$ равно 8. Таким образом, наименьшее возможное число состоит не менее чем из восьми знаков. Остается заметить, что число 13 264 513 удовлетворяет условию задачи, а поскольку оно начинается с 1, то это число и будет наименьшим.


Ответ

13 264 513.

Источники и прецеденты использования

олимпиада
Название Московская математическая олимпиада
год
Номер 84
Год 2021
класс
Класс 11
задача
Номер 3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .