Страница:
<< 5 6 7 8 9 10 11 >> [Всего задач: 77]
|
|
|
Сложность: 4
Классы: 8,9,10
|
Дана последовательность
...,
a-n,...,
a-1,
a0,
a1,...,
an,...
бесконечная в обе стороны, причём каждый её член равен
суммы
двух соседних. Доказать, что если какие-то два её члена равны, то в ней есть
бесконечное число пар равных между собой чисел. (Пояснение: два члена, про
которые известно, что они равны, не обязательно соседние).
Решение
Пусть
ai=aj для некоторых
i<j . Докажем тогда, что
ai+k=aj-k для
всех
k – из этого будет следовать утверждение задачи.
Докажем это вначале для
1
k j-i-1
. Пусть число
k из этого промежутка таково, что
величина
|ai+k-aj-k| максимальна. Тогда
4
|ai+k-aj-k|=|ai+k-1
+ai+k+1
-aj-k-1
-aj-k+1
|
|ai+k-1
-aj-k-1
|+|ai+k+1
-aj-k+1
| 2
|ai+k-aj-k| .
Следовательно,
|ai+k-aj-k|=0
. Поскольку мы выбрали разность
с максимальным модулем, то
ai+k=aj-k для любого
1
k j-i-1
.
Теперь индукцией по
k легко доказать, что
ai+k=aj-k при всех
k ,
поскольку из равенств
ai-k+2
=aj+k-2
и
ai-k+1
=aj+k-1
следует равенство
ai-k+2
=aj+k-2
.
В некотором царстве, в некотором государстве было выпущено неограниченное
количество монет достоинством в n1, n2, n3, ... копеек, где
n1 < n < 2 < n3 < ... – бесконечная последовательность, состоящая из натуральных чисел. Докажите, что эту последовательность можно оборвать, то есть найдётся такое число N, что любую сумму, которую можно уплатить без сдачи выпущенными монетами, на самом деле можно уплатить только монетами достоинством в n1, n2, ..., nN копеек.
Решение
Обозначим через d наибольший общий делитель всех данных чисел и через ds – наибольший общий делитель чисел n1, n2, ..., ns. Поскольку
d1 ≥ d2 ≥ d3 ≥ ..., то dk = dk+1 = ... = d для некоторого k ≥ 2. Возьмём числа n1, ..., nk и рассмотрим все суммы, которые можно уплатить этими монетами. Эти суммы, расположенные в порядке возрастания, с какого-то места образуют арифметическую прогрессию с разностью dk = d; эту же арифметическую прогрессию образуют и суммы, полученные из первоначального бесконечного набора монет {ni}, 1 ≤ i < ∞. Поэтому, добавив к монетам n1, ..., nk необходимое количество монет nk+1, ..., nN, не попадающих в
указанную арифметическую прогрессию, получаем искомый конечный набор монет
n1, n2, ..., nN, которыми можно уплатить все возможные суммы, образованные из исходного набора монет n1, n2, n3, ... .
Неутомимые Фома и Ерёма строят последовательность. Сначала в последовательности
одно натуральное число. Затем они по очереди выписывают следующие числа: Фома
получает очередное число, прибавляя к предыдущему любую из его цифр, а Ерёма – вычитая из предыдущего любую из его цифр. Докажите, что какое-то число в этой последовательности повторится не меньше 100 раз.
Решение
Пусть первые два члена a1 и a2 последовательности меньше 10m. Докажем, что тогда и все остальные члены меньше 10m. Предположим противное и обозначим через n наименьший номер, при котором an ≥ 10m. Ясно, что этот член написан Фомой и an–1 ≥ 10m – 9. Тем более, an–2 ≥ 10m – 9, то есть все цифры числа an–2, кроме последней, – девятки. Но тогда Ерёма, вычитая из этого числа одну из его цифр, получит an–1 ≤ 10m – 10. Противоречие.
В силу бесконечности количества членов последовательности и конечности множества её значений по крайней мере один из её членов повторится бесконечное число раз.
|
|
|
Сложность: 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) следует, что в ней встречаются и все натуральные числа.
|
|
|
Сложность: 4+
Классы: 8,9,10
|
Существует ли такая последовательность натуральных чисел, чтобы любое
натуральное число 1, 2, 3, ... можно было представить единственным способом
в виде разности двух чисел этой последовательности?
Решение
Ответ: такая последовательность существует. Объясним коротко, как её
построить. Предположим, что мы построили конечную последовательность, обладающую
следующими свойствами:
- все попарные разности между членами этой последовательности различны;
- числа 1, 2, ..., k можно представить в виде разности двух её членов.
- число k + 1 нельзя представить в виде разности двух её членов.
Пусть максимальный член этой последовательности равен
M. "Допишем"
теперь эту последовательность: добавим к ней числа 2
M и 2
M +
k + 1. Проверьте сами, что новая последовательность удовлетворяет свойствам 1, 2 (с заменой
k на
k +
i, где
i — некоторое натуральное число, зависящее от
первоначально построенной последовательности,
i ≥ 1) и свойству 3 (с
заменой числа
k + 1 на число
k +
i + 1). Применяя описанное "дописывание", например, к числам 1, 2, получим бесконечную
последовательность, удовлетворяющую условиям задачи.
Страница:
<< 5 6 7 8 9 10 11 >> [Всего задач: 77]
Фильтр
