ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Страница: << 5 6 7 8 9 10 11 >> [Всего задач: 77]
Неутомимые Фома и Ерёма строят последовательность. Сначала в последовательности одно натуральное число. Затем они по очереди выписывают следующие числа: Фома получает очередное число, прибавляя к предыдущему любую из его цифр, а Ерёма – вычитая из предыдущего любую из его цифр. Докажите, что какое-то число в этой последовательности повторится не меньше 100 раз. Решение Пусть первые два члена a1 и a2 последовательности меньше 10m. Докажем, что тогда и все остальные члены меньше 10m. Предположим противное и обозначим через n наименьший номер, при котором an ≥ 10m. Ясно, что этот член написан Фомой и an–1 ≥ 10m – 9. Тем более, an–2 ≥ 10m – 9, то есть все цифры числа an–2, кроме последней, – девятки. Но тогда Ерёма, вычитая из этого числа одну из его цифр, получит an–1 ≤ 10m – 10. Противоречие.
Рассмотрим последовательность, первые два члена которой равны 1 и 2 соответственно, а каждый следующий член – это наименьшее натуральное число, которое еще не встретилось в последовательности и которое не взаимно просто с предыдущим членом последовательности. Докажите, что каждое натуральное число входит в эту последовательность. Решение 1) Для данного числа n меньшие числа занимают в последовательности конечное число мест. Если после них встречается число m, не взаимно простое с n, и к этому моменту число n ещё не встретилось, то n будет написано сразу после m. Таким образом, чтобы гарантировать наличие в последовательности числа n, достаточно доказать, что в последовательности встретится бесконечное количество чисел, не взаимно простых с n.
РешениеОтвет: такая последовательность существует. Объясним коротко, как её построить. Предположим, что мы построили конечную последовательность, обладающую следующими свойствами:
В последовательности натуральных чисел {an}, n = 1, 2, ..., каждое натуральное число встречается хотя бы один раз, и для любых различных n и m выполнено неравенство Докажите, что тогда |an – n| < 2000000 для всех натуральных n. РешениеИз неравенства в условии следует, что все члены последовательности попарно различны. Лемма. Если i > n и ai < an, то i – n < 2000000. По условию в последовательности встречаются все натуральные числа, значит, 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.
Существует ли такая бесконечная возрастающая последовательность a1, a2, a3, ... натуральных чисел, что сумма любых двух различных членов последовательности взаимно проста с суммой любых трёх различных членов последовательности? Решение Положим a1 = 1, an+1 = (3an)! + 1. Заметим, что все эти числа нечётны. Для того, чтобы показать, что эта последовательность удовлетворяет требованиям, нам придётся эти требования несколько усилить. Будем говорить, что пара (тройка) чисел хорошая, если все её элементы, отличные от единицы, различны (а единица может встретиться в ней несколько раз). Докажем следующее утверждение. ОтветСуществует.
Страница: << 5 6 7 8 9 10 11 >> [Всего задач: 77] |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|