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

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

Условие

В бесконечной последовательности  a1, a2, a3, ... число a1 равно 1, а каждое следующее число an строится из предыдущего an–1 по правилу: если у числа n наибольший нечётный делитель имеет остаток 1 от деления на 4, то  an = an–1 + 1,  если же остаток равен 3, то  an = an–1 – 1.  Докажите, что в этой последовательности
  а) число 1 встречается бесконечно много раз;
  б) каждое натуральное число встречается бесконечно много раз.
(Вот первые члены этой последовательности: 1, 2, 1, 2, 3, 2, 1, 2, 3, 4, 3, ...)

Решение

  а) Пусть  an = an–1 + bn.  Тогда  an = 1 + b2 + ... + bn.  Заметим, что  b2n = bn.  Отсюда
a4n = 1 + b2 + ... + b4n = b2 + b4 + ... + b4n + (1 + b3) + (b5 + b7) + ... + (b4n–3 + b4n–1) = 1 + b2 + b3 + ... + b2n = a2n  (выражения в скобках равны нулю).
  Поэтому  a2n = a2 = 2,  следовательно,  a2n–1 = 1.

  б) Согласно а)  a16n+4 = a8n+2 = a8n+1 + 1 = a8n + 2 = a4n + 2.  Это значит, что члены с индексами, кратными 4, могут быть сколь угодно большими.
  Теперь утверждение задачи следует из п. а) и дискретной непрерывности.

Замечания

1. Нетрудно доказать по индукции (см. решения Задачника "Кванта" задача М2119), что an равно количеству групп нулей и единиц в двоичной записи числа n. Например, если  n2 = 1110011001  – 3 группы единиц и 2 группы нулей, то  an = 5.

2. В варианте 10-11 классов предлагался только п. б).

3. Баллы: 8-9 кл. – 5 + 5, 10 кл. – 8.

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

олимпиада
Название Турнир городов
Турнир
Дата 2008/2009
Номер 30
вариант
Вариант осенний тур, сложный вариант, 10-11 класс
задача
Номер 5
олимпиада
Название Турнир городов
Турнир
Дата 2008/2009
Номер 30
вариант
Вариант осенний тур, сложный вариант, 8-9 класс
задача
Номер 7

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

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