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

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Задачи

Страница: << 5 6 7 8 9 10 11 >> [Всего задач: 73]      



Задача 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) следует, что в ней встречаются и все натуральные числа.
Прислать комментарий


Задача 79286

Темы:   [ Последовательности (прочее) ]
[ Принцип крайнего (прочее) ]
[ Процессы и операции ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 4+
Классы: 8,9,10

Автор: Лифшиц А.

Существует ли такая последовательность натуральных чисел, чтобы любое натуральное число 1, 2, 3, ... можно было представить единственным способом в виде разности двух чисел этой последовательности?

Решение

Ответ: такая последовательность существует. Объясним коротко, как её построить. Предположим, что мы построили конечную последовательность, обладающую следующими свойствами:

  1. все попарные разности между членами этой последовательности различны;
  2. числа 1, 2, ..., k можно представить в виде разности двух её членов.
  3. число k + 1 нельзя представить в виде разности двух её членов.
Пусть максимальный член этой последовательности равен M. "Допишем" теперь эту последовательность: добавим к ней числа 2M и 2M + k + 1. Проверьте сами, что новая последовательность удовлетворяет свойствам 1, 2 (с заменой k на k + i, где i — некоторое натуральное число, зависящее от первоначально построенной последовательности, i ≥ 1) и свойству 3 (с заменой числа k + 1 на число k + i + 1). Применяя описанное "дописывание", например, к числам 1, 2, получим бесконечную последовательность, удовлетворяющую условиям задачи.
Прислать комментарий

Задача 109941

Темы:   [ Последовательности (прочее) ]
[ Системы алгебраических неравенств ]
[ Монотонность и ограниченность ]
Сложность: 5-
Классы: 9,10,11

Автор: Храмцов Д.

В последовательности натуральных чисел {an},  n = 1, 2, ...,  каждое натуральное число встречается хотя бы один раз, и для любых различных n и m выполнено неравенство     Докажите, что тогда  |an – n| < 2000000  для всех натуральных n.

Решение

  Из неравенства в условии следует, что все члены последовательности попарно различны.

  Лемма. Если  i > n  и  ai < an,  то  i – n < 2000000.
  Доказательство. Отрезок  [1, an]  содержит лишь конечное число членов последовательности, значит, все ak с достаточно большими номерами k будут больше an. При возрастании индекса от i до бесконечности найдётся такое j, что  aj < an < aj+1.  Расстояние между aj и aj+1 по условию меньше 1998, поэтому либо  an – aj < 999,  либо  aj+1an < 999. . В первом случае,  |j – n| < 1998(an – aj) < 1998·999,  значит,  i ≤ j < n + 1998·999 < n + 2·106,  во втором аналогично  i < j < n – 1 + 1998·999 < n + 2·106.

  По условию в последовательности встречаются все натуральные числа, значит, an равно числу членов последовательности, лежащих на отрезке  [1, an].  Член последовательности, лежащий на отрезке  [1, an],  имеет индекс не больше n или больше n, количество первых не более n, количество вторых, по доказанному, меньше 2·106. Значит,  an < n + 2·106.  С другой стороны, также по доказанному, если  i < n – 2·106,  то  ai < an,  значит, в отрезке  [1, an]  содержится больше  n – 2·106  членов последовательности. Таким образом,  n – 2·106 < an < n + 2·106,  откуда  |an – n| < 2·106.
Прислать комментарий


Задача 66150

Темы:   [ Последовательности (прочее) ]
[ НОД и НОК. Взаимная простота ]
[ Индукция (прочее) ]
[ Примеры и контрпримеры. Конструкции ]
Сложность: 5
Классы: 9,10,11

Существует ли такая бесконечная возрастающая последовательность a1, a2, a3, ... натуральных чисел, что сумма любых двух различных членов последовательности взаимно проста с суммой любых трёх различных членов последовательности?

Решение

  Положим  a1 = 1,  an+1 = (3an)! + 1.  Заметим, что все эти числа нечётны. Для того, чтобы показать, что эта последовательность удовлетворяет требованиям, нам придётся эти требования несколько усилить. Будем говорить, что пара (тройка) чисел хорошая, если все её элементы, отличные от единицы, различны (а единица может встретиться в ней несколько раз). Докажем следующее утверждение.
  Лемма. Пусть  (ai, aj)  и  (ap, aq, ar)  – хорошие пара и тройка элементов указанной последовательности. Тогда
(ai + aj, ap + aq + ar) = (ai + aj, ap + aq – ar) = 1.
  Доказательство проведём индукцией по наибольшему индексу m среди i, j, p, q и r. База  (m = 1)  очевидна.
  Шаг индукции. Пусть  m > 1.  Число am лежит либо только в паре  (ai, aj),  либо только в тройке  (ap, aq, ar),  либо в обеих.
  1) Пусть am – только элемент пары; скажем,  am = ai.  Тогда, поскольку  0 < |ap + aq ± ar| ≤ 3ai–1,  число  am – 1 = (3am–1)!  делится на  ai + aq ± ar,  то есть  (ai + am, ap + aq ± ar) = ((ai + 1) + (am – 1), ap + aq ± ar) = (ai + a1, ap + aq ± ar) = 1  по предположению индукции.
  2) Пусть am – только элемент тройки; скажем,  am = aq.  Аналогично  am – 1  делится на  ai + aj,  так что
(ai + aj, ap + am ± ar) = (ai + aj, ap + a1 ± ar) = 1  по предположению индукции.
  3) Пусть am – элемент и пары, и тройки; скажем,  am = aj = aq.  Тогда  am – 1  делится на  ap – ai ± ar,  так что
(ai + am, ap + am ± ar) = (ai + am, (ap + am ± ar) – (ai + am)) = (ai + am, ap – ai ± ar) = (ai + a1, ap – ai ± ar) = 1  по предположению индукции.

Ответ

Существует.

Прислать комментарий

Задача 77948

Темы:   [ Последовательности (прочее) ]
[ Перебор случаев ]
Сложность: 5
Классы: 9,10

Дана последовательность целых чисел, построенная следующим образом: a1 — произвольное трёхзначное число, a2 — сумма квадратов его цифр, a3 — сумма квадратов цифр числа a2 и т.д. Докажите, что в последовательности a1, a2, a3, ...обязательно встретится либо 1, либо 4.

Решение

Прежде всего заметим, что a2$ \le$92 . 3 = 243, а значит, a3$ \le$22 + 92 . 2 = 166. Если 100$ \le$a3$ \le$166, то a4$ \le$1 + 62 + 92 = 118, а если 100$ \le$a4$ \le$166, то a5$ \le$2 + 64 < 100. Поэтому достаточно проверить требуемое утверждение лишь для чисел, не превосходящих 99. Это делается непосредственной проверкой. Мы будем выписывать последовательность до тех пор пока не встретится 1, 4 или число, уже встречавшееся ранее. При этом мы будем учитывать, что перестановка цифр и добавление (удаление) нуля не влияет на дальнейшие члены последовательности. В результате получим следующие последовательности: 2, 4; 3, 9, 81, 65, 61, 37, 58, 89, 145, 42, 20, 4; 5, 25, 29, 85; 6, 36, 45, 41, 17, 50; 7, 49, 97, 130, 10; 8, 64, 42; 11, 2; 12, 5; 15, 26, 40; 19, 82, 68, 100; 27, 53, 34, 25; 33, 36; 35, 34; 38, 73; 39, 90; 44, 32; 47, 65; 48, 80; 55, 50; 57, 74; 59, 106; 66, 72; 67, 85; 69, 117, 51; 77, 98; 78, 113, 11; 88, 128, 69; 99, 162, 41.
Прислать комментарий


Страница: << 5 6 7 8 9 10 11 >> [Всего задач: 73]      



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

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