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

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

Условие

Дана арифметическая прогрессия (с разностью, отличной от нуля), составленная из натуральных чисел, десятичная запись которых не содержит цифры 9.
  а) Докажите, что число её членов меньше 100.
  б) Приведите пример такой прогрессии с 72 членами.
  в) Докажите, что число членов всякой такой прогрессии не больше 72.


Решение

  Можно считать, что разность d прогрессии положительна и не кратна 10. Пусть d – k-значное число.

  а) Числа от A890...0 до A9...9  (k + 2  девятки) все содержат девятки. Их больше d. Расстояние между двумя последовательными группами таких чисел равно  89·10k ≤ 89d.  Следовательно, членов последовательности не больше 90.

  в) При переходе от какого-либо члена последовательности к следующему, то есть при прибавлении числа d, (k+1)-й разряд либо не изменяется, либо увеличивается на 1 (цифра 9 запрещена, поэтому случай изменения разряда с цифры 9 на 0 исключается). Если в прогрессии нет переходов со сменой (k+1)-го разряда, то членов прогрессии не больше 9. Пусть такие переходы есть. Так как цифра 9 запрещена, то их не больше 8. Между двумя такими переходами, а также перед первым и после последнего идут группы (может быть, пустые) переходов без смены (k+1)-го разряда. Всего таких групп – 9.
  Рассмотрим член прогрессии, стоящий перед переходом, меняющим (k+1)-й разряд. Так как он не содержит 9, то его k-значный "хвост" (остаток от деления на 10k) не больше  .  Но при прибавлении d должен произойти перенос. Следовательно,  d > .
  Рассмотрим такую группу членов нашей прогрессии  am, am+1, ..., am+L,  что (k+1)-й разряд не меняется. Тогда k-значные хвосты сами образуют арифметическую прогрессию с той же разностью:  bm, bm+1, ..., bm+L.  Но  bm ≥ 0,  bm+L = bm + dL,  отсюда  L ≤ 7.
  Итак, всего членов прогрессии не больше чем  7·9 + 8 + 1 = 72.

  б) Пример нужной прогрессии даёт прогрессия с первым членом 1 и разностью 125. Её 72-й член равен 8876.

Замечания

Баллы: 3 + 3 + 4

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

олимпиада
Название Турнир городов
Турнир
Дата 1991/1992
Номер 13
вариант
Вариант осенний тур, основной вариант, 10-11 класс
Задача
Номер 6

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

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