Тема ММО (Московская математическая олимпиада)

Последовательности и прогрессии на ММО

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела ммо (московская математическая олимпиада)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#67675

Назовём тройку чисел триплетом, если одно из них равно среднему арифметическому двух других. Последовательность $(a ) n$ строится следующим образом: $a1 = a2 = 1$ и при $n> 2$ число $an$ — такое минимальное натуральное число, что среди чисел $a1,a2,...,an$ нет трёх, образующих триплет. Докажите, что $n2 +7 an ≤--8--$ для любого $n.$

Источники: ММО-2023, 11.6 (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 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 <= С²ₓ₋₁. Это и является противоречием.

Показать доказательство

Очевидно, что последовательность не убывает. Действительно, неравенство $a > a n n+1$ противоречило бы выбору $a . n$ Также понятно, что любое число повторяется не более, чем дважды, иначе в последовательности найдутся три одинаковых числа, а они образуют триплет. Теперь легко видеть, что если число $c$ впервые встречается в последовательности в качестве $an,$ то $an+1 = an = c.$

Таким образом, для любого натурального $k$ верно равенство $a2k−1 = a2k.$ Заметим, что тогда достаточно доказать требуемое неравенство только для нечетных индексов:

(2k− 1)2 +7 (2k)2+7 a2k = a2k− 1 ≤---8-----≤ ---8---

Положим $bk = a2k−1.$ Тогда нужно доказать, что

2 bk ≤ (2k− 1)-+-7= k(k− 1)+ 1 8 2

Отметим, что последовательность $(bn)$ обладает тем свойством, что при $k> 1$ очередной член последовательности $bk$ - минимальное натуральное число, которое не образует триплет с парами чисел из ${b1,...,bk−1},$ где пара может иметь вид $(bi,bi).$ При этом $bk > bk−1,$ то есть $(bn)$ строго возрастает, в отличие от $(an).$

Пусть $n$ - минимальное натуральное число, для которого требуемое неравенство неверно, то есть $bn > n(n−21)+1.$ Это означает, что среди чисел от $1$ до $n(n−21)+ 1$ содержится ровно $n− 1$ член последовательности, поскольку при $m < n$ по предположению имеем

bm ≤ m(m-− 1) +1< n(n−-1)+ 1 2 2

Обозначим через $s$ количество чисел в промежутке от 1 до $n(n−1)+ 1, 2$ не принадлежащих последовательности $(bn).$ Тогда

s= n(n-− 1)+ 1− (n − 1)= (n−-1)(n−-2)+ 1= C2n−1+1 2 2

Обозначим эти числа $di,1≤ i≤ s.$ В силу минимальности каждого из $bm$ для любого $1≤ k≤ s$ найдутся такие числа $bik,bjk,$ где $ik ≤ jk ≤ n− 1,$ что $(bik,bjk,dk)$ - триплет. При это можно считать, что $dk$ - наибольший элемент в триплете, иное бы противоречило выбору наименьшего элемента последовательности $(bn),$ большего $dk.$ Отсюда $ik < jk.$ Тогда число способов выбрать пару $(ik,jk)$ не превосходит $C2n−1,$ то есть не больше способов выбрать два различных индекса из ${1,2,...,n− 1}.$ В то же время парами $(ik,jk)$ нужно обеспечить $s>C2n−1$ чисел $di.$ Полученное противоречие завершает решение.

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 2#67677

Какое наименьшее количество различных целых чисел нужно взять, чтобы среди них можно было выбрать как геометрическую, так и арифметическую прогрессию длины 5?

Источники: ММО-2023, 11.2 (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Понятно, что чисел хотя бы 5. Немного пописав, приходим к выводу: задача была бы слишком простой, если бы ответ был бы 5 и пример находился бы просто. Поэтому попробуем доказать, что чисел хотя бы 6. Попробуем от противного, а далее попробуем найти пример на 6.

Подсказка 2

Раз уж доказываем от противного, как-то стоит эти числа записать. Работать с числами из геометрической последовательности удобнее, поэтому запишем все 5 членов через первый член и знаменательно прогрессии. Для каких из них можно записать условие на принадлежность к одной арифметической прогрессии?

Подсказка 3

Для первого, третьего и пятого члена геометрической последовательности. Помним, что удвоенный член арифметической последовательности равен сумме его соседей. Попробуем с помощью преобразований прийти к противоречию. Теперь немного попишем и попробуем найти пример на 6!

Подсказка 4

Ясно, что нам нужны и отрицательные числа тоже, тогда в геометрической прогрессии знаки членов будут противоположны. Искать среди больших чисел ну очень неудобно, поэтому попробуем найти какие-то маленькие числа, например, 1 и т.д...

Показать ответ и решение

(Оценка) Покажем, что никакие пять различных чисел не удовлетворяют условию задачи. Предположим противное: пусть найдутся пять различных целых чисел, одновременно образующих геометрическую и (возможно в другом порядке) арифметическую прогрессию. Тогда они имеют вид $2 3 4 b,bq,bq,bq,bq,$ где $b ∈ℤ.$ Заметим, что $b ⁄=0,q ⁄= 0$ по определению геометрической прогрессии. Числа $2 4 b,bq ,bq$ всегда одного знака и в арифметической прогресии идут либо подряд при $q < 0,$ либо через одного при $q < 0.$ В любом случае должно выполняться равенство $2 4 2bq =b +bq,$ т.е. $2 2 b(q − 1) = 0,$ откуда $q = ±1,$ но тогда среди чисел есть равные. Противоречие. Следовательно, пяти чисел недостаточно.

(Пример) Приведём пример шести целых чисел, удовлетворяющих условию:

−8,−2,1,4,10,16

Действительно, числа $1,−2,4,−8,16$ образуются геометрическую прогрессию, а числа $− 8,−2,4,10,16$ - арифметическую прогрессию.

Ответ: 6

Ошибка.
Попробуйте повторить позже

Задача 3#31351

Даны две непостоянные прогрессии $(a ) n$ и $(b), n$ одна из которых арифметическая, а другая — геометрическая. Известно, что $a1 = b1,a2 :b2 = 2$ и $a4 :b4 =8.$ Чему может быть равно отношение $a3 :b3?$

Источники: ММО-2017, 11.1, автор - Д.В. Горяшин, (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Вообще, у нас есть два случая: когда a_i - арифм. прогрессия, b_i - геом, и наоборот. Давайте в обоих случаях обозначим T - первые члены, d - разность арифм.прогрессии, q - разность геом.прогрессии. Как в первом случае будут переписаны условия через T, d и q?

Подсказка 2

Если подставить одно условие в другое, то можно получить уравнение на q! Проверьте все случаи, чему может быть равно q, и останется выразить d и третьи члены прогрессий

Подсказка 3

Теперь остаётся проверить второй случай: a_i - геом. прогрессия, b_i - арифм. прогрессия. Также перепишите условия, которые вам даны, в терминах T, d и q, и подставьте одно в другое)

Показать ответ и решение

Пусть $a = b = a⁄= 0 1 1$ , разность арифметической прогрессии равна $d$ , а знаменатель геометрической равен $q$ . Поскольку прогрессии непостоянны, $d⁄= 0$ и $q ⁄= 1$ . Возможны два случая:

1) Пусть $(an)$ — арифметическая прогрессия, а $(bn)$ — геометрическая. Тогда по условию получаем

3 a+ d= 2aq,a+ 3d= 8aq

d= a(2q− 1)

3d= a(8q3− 1)= d(4q2+ 2q+1)

2q2+q − 1= 0

q = 1 или q = −1 2

Если $q = 1∕2$ , то $d =a(2q− 1)= 0$ , что по условию невозможно.

Если $q = −1$ , то $d= −3a$ и $a3 :b3 = aa+q2d2-=− 5.$

2) Пусть теперь $(an)$ — геометрическая, а $(bn)$ — арифметическая прогрессия. Тогда

2(a+ d)= aq,8(a +3d)= aq3

2d= a(q− 2)

24d= a(q3− 8)= 2d (q2+ 2q+4)

2 q + 2q − 8= 0

q = 2 или q = −4

В первом случае снова $d= 0$ , что противоречит условию, а во втором $q = −4,d= −3a$ и $a3 :b3 = aa+q22d-=− 156 .$

Ответ:

$− 5$ или $− 16 5$

Ошибка.
Попробуйте повторить позже

Задача 4#40087

Последовательность $(a ) n$ такова, что $a = n2 n$ при $1≤ n ≤5$ и при всех натуральных $n$ выполнено равенство $a +a = a + a . n+5 n+1 n+4 n$ Найдите $a2015.$

Источники: ММО-2015, 11.1, автор - С.Б.Гашков, (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1!

Какие-то странные условия, попробуем получить из них что-то хорошее. Если вы знаете что-то про начальные члены последовательности, а еще про то, как они соотносятся с предыдущими, здорово бы было как-то выразить большие члены через члены от 1 до 5. Получить на них какое-то правило.

Подсказка 2!

Давайте напишем. a(n+5) +a(n+1) = a(n+4) + a(n). Заметим, что индексы в обеих частях отличаются на 4. Напишем a6+a2 = a5+a1 = чему-то, что мы уже знаем! Так, а может не только для а6+а2 мы знаем это равенство?

Подсказка 3!

Да, для всех чисел, отличающихся на 4 по номеру, мы поняли их сумму. Теперь вспомним, что мы ищем 2015. К сожалению, 2019 или 2011 мы не знаем. Попробуем получить еще что-то из условия с равенством. Попробуйте сделать так, чтобы и в левой, и в правой части оказалось одинаковое число.

Подсказка 4!

Да, подставим а(n+8) + а(n+4) = a(n+4)+an. Осталось сделать выводы и применить наши полученные знания :)

Показать ответ и решение

Из условия следует

2 2 an+4+ an = an+3 +an−1 = ...= a6+ a2 =a5 +a1 = 5 + 1 =26

А также

an+8+ an+4 =an+4+ an =⇒ an+8 = an

То есть значение $an$ зависит только от остатка $n$ по модулю $8,$ отсюда

a2015 =a7 = 26− a3 = 26 − 32 = 17

Ответ:

$17$

Ошибка.
Попробуйте повторить позже

Задача 5#73118

Найдите $x , 1000$ если $x = 4,x = 6 1 2$ и при любом натуральном $n ≥ 3,$ $x n$ — наименьшее составное число, большее $2x − x . n−1 n− 2$

Показать ответ и решение

Запишем условие для $n =3 :$ $x > 2⋅6 − 4 =8, 3$ откуда $x = 9. 3$ Далее, $x > 2⋅9− 6= 12 =⇒ x = 14, 4 4$ затем $x5 > 2⋅14− 9= 19 =⇒ x5 = 20.$ Можно продолжить, а можно сразу выразить $n(n+3) xn = 2 ,n ≥4.$ Нетрудно видеть, что для $n≥ 4$ такое число всегда будет составным, поэтому остаётся показать, что для $n ≥5$ (заметим, что для $n= 4$ это не выполнено) сохраняется равенство $2⋅xn−1− xn−2+1 =xn$

(n− 1)(n+ 2) (n − 2)(n +1) n(n+ 3) 2⋅-----2-----− ----2-----+ 1= ---2--- ⇐ ⇒

2n2+ 2n− 4− n2+n +2+ 2= n2+ 3n ⇐⇒ 0= 0

Итак, мы проверили, что $xn−1− xn− 2+1 =xn,n≥ 5,$ при этом $n(n+3) xn = 2$ — составное, поэтому мы нашли нужную последовательность, остаётся посчитать

1000⋅1003 x1000 =----2---= 501500

Ответ:

$501500$

Ошибка.
Попробуйте повторить позже

Задача 6#74873

Найдите $x , 1000$ если $x = 4,x = 6 1 2$ и при любом натуральном $n≥ 3,x n$ — наименьшее составное число, большее $2x − x . n−1 n−2$

Показать ответ и решение

Докажем по индукции, что $x = 1n(n+ 3). n 2$

База. При $n= 3, 4$ формула верна: $2x2− x1 = 8,$ то есть $x3 =9$ ; $2x3− x2 = 12,$ то есть $x4 = 14.$

Шаг индукции.

1 1 1 2xn− xn−1 =2⋅ 2n(n +3)− 2(n − 1)(n +2)= 2(n+ 1)(n+ 4)− 1

По условию, $xn+1$ – первое составное число, большее чем $1 2(n+ 1)(n+ 4)− 1.$ Но число $1 2(n +1)(n +4)$ – составное. Действительно, если $n$ нечётно, то $12(n +1)(n +4)=$
$(n+ 4)⋅ 12(n +1).$ Каждый из сомножителей – целое число, большее $2.$ Аналогично рассматривается случай чётного $n.$

Итак, $xn+1 = 12(n+ 1)(n+ 4).$ Подставляя $n= 1000,$ получаем $x1000 = 500⋅1003.$

Ответ:

$500⋅1003$

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 7#91361

По целому числу $a$ построим последовательность

a1 =a, a2 =1 +a1, a3 = 1+ a1a2, a4 =1+ a1a2a3, ...

(каждое следующее число на 1 превосходит произведение всех предыдущих). Докажите, что разности её соседних членов $(an+1 − an)$ - квадраты целых чисел.