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

Проект МЦНМО
при участии
школы 57
Задача 66121
Темы:    [ Десятичная система счисления ]
[ Арифметика остатков (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

При каких натуральных n для каждого целого  k ≥ n  найдётся кратное n число с суммой цифр k?

Решение

  Если n кратно 3, то всякое кратное n число кратно и 3. Значит, сумма цифр этого числа кратна 3, поэтому не может быть равной, например,  n + 1.
  Далее считаем, что n не кратно 3. Тогда найдётся решение сравнения  9x ≡ – k (mod n)  в интервале  0 < x ≤ n ≤ k.
  Если n взаимно просто с 10, то  10a ≡ 1 (mod n)  при некотором натуральном a. Тогда подойдёт число
10(10a + 102a + ... + 10xa) + (10a + 102a + ... + 10(k–x)a)  (при  k = x  вторая скобка отсутствует). Его сумма цифр равна  x + (k – x) = k,  а по модулю n оно сравнимо с  10x + (k – x) ≡ 0.
  Если же  n = 2b5cd,  где d взаимно просто с 10, то  k ≥ d.  Как показано выше, существует кратное d число с суммой цифр k. Домножив его на 10max(b,c), получим искомое число.


Ответ

При n, не кратных 3.

Замечания

10 баллов

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

олимпиада
Название Московская математическая олимпиада
год
Номер 80
Год 2017
класс
Класс 10
задача
Номер 5
олимпиада
Название Турнир городов
номер/год
Номер 38
Дата 2016/17
вариант
Вариант весенний тур, сложный вариант, 10-11 класс
задача
Номер 6

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

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