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

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

Условие

Рассмотрим последовательность, первые два члена которой равны 1 и 2 соответственно, а каждый следующий член – это наименьшее натуральное число, которое еще не встретилось в последовательности и которое не взаимно просто с предыдущим членом последовательности. Докажите, что каждое натуральное число входит в эту последовательность.


Решение

  1) Для данного числа n меньшие числа занимают в последовательности конечное число мест. Если после них встречается число m, не взаимно простое с n, и к этому моменту число n ещё не встретилось, то n будет написано сразу после m. Таким образом, чтобы гарантировать наличие в последовательности числа n, достаточно доказать, что в последовательности встретится бесконечное количество чисел, не взаимно простых с n.
  2) Докажем, что для любого N в последовательности присутствует чётное число, большее N. Начиная с какого-то места все члены последовательности больше N. На этом "участке" последовательность не может все время убывать, поэтому на нём найдётся число k, за которым следует большее число m. Если одно из чисел k, m чётно, то все в порядке. В противном случае чётное число  k + НОД(k, m),  меньшее m и не взаимно простое с k, уже присутствует в последовательности.
  Итак, последовательность содержит бесконечное количество чётных чисел.
  3) Из 1) и 2) следует, что в последовательности встречаются все чётные числа. Теперь из 1) следует, что в ней встречаются и все натуральные числа.

Замечания

1. Задача заимствована из статьи "The EKG Sequence" (J.C. Lagarias, E. M. Rains, N.J.A. Sloane). Буквы "EKG" означают "электрокардиограмма".

2. 8 баллов.

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

журнал
Название "Квант"
год
Год 2003
выпуск
Номер 3
Задача
Номер М1863
олимпиада
Название Турнир городов
Турнир
Дата 2002/2003
Номер 24
вариант
Вариант осенний тур, основной вариант, 10-11 класс
Задача
Номер 6

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

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