Ошибка.
Попробуйте повторить позже
Назовём тройку чисел триплетом, если одно из них равно среднему арифметическому двух других. Последовательность 
строится
следующим образом: 
и при 
число 
— такое минимальное натуральное число, что среди чисел 
нет трёх,
образующих триплет. Докажите, что 
для любого 
Источники:
Подсказка 1
Попробуем для начала понять, какими свойствами обладает наша последовательность. Что мы можем сказать про два подряд идущих члена? Какой из них может быть больше или равен другому?
Подсказка 2
Если aₓ > aₓ₊₁, то при выборе x элемента последовательности мы бы взяли aₓ₊₁, а не aₓ. Отсюда следует, что наша последовательность не убывает. Причем, если какое-то натуральное число n встретилось в последовательности в первый раз, следующий элемент последовательности будет также равен n. Может тогда некоторые элементы можно выкинуть...
Подсказка 3
Мы уже поняли, что наша последовательность не убывает и при этом a₂ₓ = a₂ₓ₋₁. Тогда требуемое неравенство можно доказать только для нечетных номеров. Введем новую последовательность {bₓ}: bₓ=a₂ₓ₋₁. Тогда нам нужно доказать, что bₓ <= ((2x-1)²+7)/8 = x(x-1)/2+1. Теперь надо подумать о том, какими свойствами обладает последовательность {bₓ} и как мы собираемся доказывать наше неравенство...
Подсказка 4
Из свойств последовательности {aₓ} вытекает, что {bₓ}- строго возрастает. Попробуйте теперь воспользоваться методом от противного вместе с принципом крайнего предположив, что bₓ- первый элемент последовательности, для которого не выполняется неравенство.
Подсказка 5
Пускай bₓ- первый элемент последовательности, для которого не выполняется неравенство. Тогда: bₓ > x(x-1)/2+1. Заметим также, что bₓ₋₁ < x(x-1)/2+1, иначе бы bₓ₋₁ >= x(x-1)/2+1 > (x-1)(x-2)/2+1, что противоречит выбору bₓ. Это означает, что среди чисел от 1 до x(x-1)/2+1 существуют все x-1 элементов последовательности (b₁, b₂, ... bₓ₋₁). Попробуйте теперь найти противоречие в количестве чисел в интервале от 1 до x(x-1)/2+1, которые не являются членами последовательности
Подсказка 6
Пускай таких чисел s штук. Тогда: s = x(x-1)/2+1-(x-1) = (x-1)(x-2)/2+1 = С²ₓ₋₁+1. Подумайте, как могло случится так, что какое-то число n (1 < n < x(x-1)/2+1)) не стало членом последовательности...
Подсказка 7
Если n не стало членом последовательности, то n образует триплет с какими-то двумя членам последовательности, меньшими bₓ. Всего таких пар С²ₓ₋₁. Т.к. каждая пара могла "забраковать" не более одного числа в промежутке от 1 до x(x-1)/2+1, то s <= С²ₓ₋₁. Это и является противоречием.
Очевидно, что последовательность не убывает. Действительно, неравенство 
противоречило бы выбору 
Также понятно,
что любое число повторяется не более, чем дважды, иначе в последовательности найдутся три одинаковых числа, а они
образуют триплет. Теперь легко видеть, что если число 
впервые встречается в последовательности в качестве 
то
Таким образом, для любого натурального 
верно равенство 
Заметим, что тогда достаточно доказать требуемое
неравенство только для нечетных индексов:
Положим 
Тогда нужно доказать, что
Отметим, что последовательность 
обладает тем свойством, что при 
очередной член последовательности 
- минимальное
натуральное число, которое не образует триплет с парами чисел из 
где пара может иметь вид 
При этом 
то есть 
строго возрастает, в отличие от 
Пусть 
- минимальное натуральное число, для которого требуемое неравенство неверно, то есть 
Это означает, что
среди чисел от 
до 
содержится ровно 
член последовательности, поскольку при 
по предположению
имеем
Обозначим через 
количество чисел в промежутке от 1 до 
не принадлежащих последовательности 
Тогда
Обозначим эти числа 
В силу минимальности каждого из 
для любого 
найдутся такие числа 
где
что 
- триплет. При это можно считать, что 
- наибольший элемент в триплете, иное бы
противоречило выбору наименьшего элемента последовательности 
большего 
Отсюда 
Тогда число
способов выбрать пару 
не превосходит 
то есть не больше способов выбрать два различных индекса из
В то же время парами 
нужно обеспечить 
чисел 
Полученное противоречие завершает
решение.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
