Тема Высшая проба

Последовательности и прогрессии на Высшей пробе

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

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

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

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

Подтемы раздела высшая проба

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

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

Задача 1#134205Максимум баллов за задание: 7

По кругу расставлены натуральные числа. Петя поделил каждое из них на натуральное число, ближайшее к среднему геометрическому соседних чисел. Оказалось, что все полученные числа — натуральные. Чему может быть равно наибольшее из них?

Источники: Высшая проба - 2024, 10.6 (см. olymp.hse.ru)

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

Подсказка 1

Попробуйте придумать несколько примеров.

Подсказка 2

Нам подойдут, например, (1;1;1), (1;1;2), (1;2;6;2;1). Какие полученные натуральные числа будут для них наибольшими?

Подсказка 3

1, 2 и 3 соответственно. Давайте попробуем доказать, что нельзя получить результат, больший 3.

Подсказка 4

Давайте предположим противное: пусть есть расстановка с отношением хотя бы 4. Попробуйте записать это в общем виде.

Подсказка 5

Пусть мы записали числа a₀, … , aₙ₋₁. Тогда без потери общности мы поделили a₀ на √(aₙ₋₁a₁) и получили хотя бы 4. Какой вывод можно сделать?

Подсказка 6

Одно из чисел корня должно быть хотя бы в 4 раза меньше a₀! Пусть это будет a₁. Попробуйте рассмотреть некоторую последовательность.

Подсказка 7

Пусть xᵢ = aᵢ / aᵢ₊₁. Чему равно произведение всех xᵢ?

Подсказка 8

Оно равно 1. Что это значит?

Подсказка 9

Найдется некоторый xᵢ, меньший 1. Значит, найдется такое j, что xⱼ ≤ 3.

Подсказка 10

Попробуйте доказать, что xⱼ = 3.

Подсказка 11

Для этого можно пойти от противного и предположить, что s — ближайшее целое число к √(aₙ₋₁a₁). Надо будет составить несколько неравенств и получить желаемое.

Подсказка 12

Теперь попробуйте оценить отношение x₀ / xⱼ.

Подсказка 13

Для этого стоит понять, чему равно xₜ / xₜ₊₁.

Подсказка 14

Цепочкой неравенств Вам надо оценить бесконечную геометрическую прогрессию конечной и получить противоречие.

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

Будем доказывать, что отношение больше 3 не бывает. Предположим противное, пусть есть расстановка с отношением хотя бы 4. И по кругу стоят числа $a0,a1...an−1.$

Без потери общности мы поделили $a0$ на $√ ------ an− 1a1$ и получили хотя бы $4.$ Тогда одно из чисел $an−1$ и $a1$ хотя бы в $4$ раза меньше $a0.$ Можно считать, что

a0 a1 ≥4

Рассмотрим последовательность

xi =-ai-- ai+1

Произведение всех $xi$ равно $1,$ поэтому найдётся $xk <1,$ а, значит, будет первый $j,$ такой что $xj ≤ 3.$

Докажем от противного, что $xj = 3.$ Пусть ближайшее целое к $√aj−-1aj+1$ — это $s,$ так как $aj$ делится на $s,$ то $s≤ aj.$

Так как $s$ ближайшее целое к $√aj−1aj+1,$ то верно неравенство

aj−1aj+1 ≤s(s+1)

Из которого следует

a a ≤a (a+ 1) j−1 j+1 j j

С другой стороны, если $xj < 3,$ то

aj aj+1 > 3

По определению же $j,$

aj−1 > 3aj

Воспользуемся этими двумя неравенствами

(aj +1)(3aj + 1) 2 aj + 1 aj− 1aj+1 ≥------3------= aj +aj +--3--> aj(aj + 1)

Это противоречие доказывает, что $xj = 3.$

Оценим отношение $xx0j.$ Для этого заметим, неравенство

xxt-= ataa2t+2 ≤ at+1(aat2+1+-1) =1 +a-1 t+1 t+1 t+1 t+1

( ) ( ) 4≤ x0 = x0x1⋅⋅⋅xj−1 < 1 +-1 ⋅⋅⋅ 1+ -1 3 xj x1x2 xj a1 aj

Заметим, что $aj$ делится на $3$ и если $aj =3,$ то неравенство не выполняется, поэтому $aj ≥ 6.$

Из определение $j$ получаем $aj−k > 3kaj.$ Получили такое числовое неравенство

4 ( 1)( -1) ( -1--) 3 ≤ 1+ 6 1+ 18 ⋅⋅⋅ 1+ 2⋅3j

3 ( 1) ( 1 ) ( 1 ) 4 ≥ 1− 7 1− 19 ⋅⋅⋅ 1− 2⋅3j +-1

Воспользуемся неравенством

(1− t1)(1 − t2)...(1− tn)≥1− t1− t2− ...− tn,

верного из-за индукции

3 1 -1 ---1--- 1 -1 -1-- 1 3 4 ≥ 1− 7 − 19 − ...− 2⋅3j + 1 > 1− 6 − 18 − ...− 2⋅3j ≥ 1− 4 = 4

В последнем неравенстве оценили конечную геометрическую прогрессию бесконечной. Получили противоречие, a, значит, предположение что отношение может быть больше или равно $4$ неверно.

Приведём примеры для $1,$ $2,$ и $3.$

1.: $1,$ $1,$ $1$
2.: $1,$ $1,$ $2$
3.: $1,$ $2,$ $6,$ $2,$ $1$

Ответ: 1, 2 и 3

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

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

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

Задача 2#92418Максимум баллов за задание: 7

Для действительного числа $α ∈(0,1)$ рассмотрим возрастающую последовательность всех натуральных чисел $m i$ , для которых ${miα} <α$ . Может ли для какого-то $α$ соответствующая последовательность начинаться с

a) $2021,4041,6062?$

б) $2021,4042,6062,8082?$

Источники: Высшая проба - 2021, 11.1 (см. olymp.hse.ru)

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

Подсказка 1

У нас задачка на последовательность, каким методом можем попробовать воспользоваться?

Подсказка 2

Действительно, вспомним математическую индукцию. Осталось придумать утверждение, которое будем доказывать. У нас есть дробная часть, но с ней работать в индукции сложно, переходы могут быть затруднены, так что попробуем обойтись без неё. Так как есть шаг индукции, то хорошо бы связать утверждение с ним тоже, ну и не забудем про наше действительное число!

Подсказка 3

Попробуем доказать, что m_i является таким наименьшим натуральным числом n_i, что α*n_i ≥ i через индукцию. Что нам это даёт в наших пунктах? Отлично, мы на финишной прямой, применим утверждение на конкретных пунктах!

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

Покажем индукцией по $i$ , что $m i$ — это наименьшее натуральное число $n i$ , для которого $n α≥ i i$ .

_________________________________________________________________________________________________________________________________________________________________________________

База: для удобства будем считать 0 натуральным числом, и все последовательности тоже начинать с нулевого члена. Тогда, во-первых, $m0 = 0$ поскольку ${0α} =0 <α$ , и 0 — первое натуральное число с таким свойством, поскольку оно просто первое. С другой стороны, $n0 = 0$ поскольку $n0α≥ 0$ и опять же, 0 — первое натуральное число с этим свойством. Итак, $m0 = n0$ .

_________________________________________________________________________________________________________________________________________________________________________________

Переход. Пусть $mi = ni$ . Тогда для всех натуральных чисел $k$ из отрезка $[ni+ 1,ni+1− 1]$ имеем $[kα]= i$ из определения $ni+1$ . Но тогда ${kα}= {niα}+ (k − ni)α≥ α$ . С другой стороны, $ni+1α= (ni+1− 1)α+ α< i+1 +α$ то есть ${ni+1α <α}$ . Итак, $mi+1 =ni+1$ .

_________________________________________________________________________________________________________________________________________________________________________________

а). Из приведенных выше рассуждений следует система неравенств (самая левая)

( 1 1 ( 1 |{ 2020 >α ≥ 2021 |{ 2020< α ≤ 2021 1 1 1 |( 42040 >α ≥ 42041 ⇔ |( 2020 < 1α ≤ 202012 ⇔ 20203 <α-≤ 20202. 63061 >α ≥ 63062 202013 < 1α ≤ 202023

Преобразуем как написано выше, благо все числа положительны. Имеем, что условие выполняется для любого $α$ , такого что $1 α$ лежит в полуинтервале $( 1 1] 20203,20202$ .

Отметим, что для решения задачи не обязательно описывать множество всех таких $α$ (как сделано выше), достаточно указать одно, например, $2 4041$ , и доказать, что оно подходит.

_________________________________________________________________________________________________________________________________________________________________________________

б) Действуя аналогично, имеем:

( 1 1 ( 1 ||||{ 2020 >α ≥ 2021 ||||{ 2020< α ≤ 2021 42041 >α ≥ 40242 ⇔ 202012 < 1α ≤ 2021 ⇔ 20201 < 1≤ 20201. ||||( 63061 >α ≥ 60362 ||||( 202013 < 1α ≤ 202023 2 α 2 84081 >α ≥ 80482 202014 < 1α ≤ 202012

Приходим к противоречию, что $1 1 20202 <20202$ , что доказывает что такого $α$ не существует.

Ответ:

а) да

б) нет

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

Задача 3#92419Максимум баллов за задание: 7

В последовательности чисел $20,21,22,...$ некоторые члены умножили на -1 , причем известно, что осталось бесконечно много положительных членов. Докажите, что любое натуральное число представимо в виде суммы нескольких различных членов полученной последовательности.

Источники: Высшая проба - 2021, 11.2 (см. olymp.hse.ru)

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

Подсказка 1

Будем доказывать по индукции. Рассмотрим операцию сокращения последовательности. Удалим первый элемент, а остальные разделим на 2. Тогда у нас останется последовательность, описанная в условии.

Подсказка 2

По индукции будем считать, что числа, меньшие n, можно представить в сокращённой последовательности. Тогда можно получить представление в исходной последовательности, умножив на 2 представление в сокращенной.

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

Будем называть последовательность, удовлетворяющую условию задачи ПУУЗ.

Заметим, что следующая операция из ПУУЗ делает ПУУЗ: из последовательности выкидываем первый член, а все остальные делим на 2. В самом деле, все члены остались плюс или минус степенями двойки, и положительных все еще бесконечно. Назовем эту операцию сокращением.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем по индукции утверждение: любое натуральное $n$ для любой ПУУЗ представляется в виде суммы некоторые ее различных членов.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем что в таком виде представляется 1. В самом деле, у любой ПУУЗ есть положительные члены, пусть первый из них $k 2$ . Тогда заметим что

( ) ( ) ( ) − 20 + −21 +⋅⋅⋅+ −2k−1 + 2k = 1

_________________________________________________________________________________________________________________________________________________________________________________

Пусть утверждение доказано для всех натуральных чисел, меньших $n$ . Рассмотрим $n ≥ 2$ и ПУУЗ $A$ . Если $n$ четное — представим $n2$ в виде суммы нескольких различных членов сокращения $A$ , этому представлению соответствует представление $n$ в виде суммы различных членов $A$ . Если $n$ нечетное -— вычтем из него первый член $A$ , (который равен 1 или -1 ) и результат поделим пополам. Мы получили одно из чисел $n±21$ , оно натуральное и строго меньше $n$ , значит для него уже доказано, что оно представляется в виде суммы различных членов произвольной ПУУЗ, в частности — сокращения $A$ . Снова строим соответствующее представление $n$ в виде суммы различных членов $A$ .

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

Задача 4#68081Максимум баллов за задание: 7

Три различных положительных числа являются тремя последовательными членами арифметической прогрессии. Могут ли эти же три числа оказаться тремя (не обязательно последовательными) членами геометрической прогрессии?

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

Попробуем подобрать пример. Пусть члены арифметической прогрессии имеют вид $a − d,a,a +d.$ Ясно, что эти числа не могут быть последовательными членами геометрической прогрессии, потому что $2 2 2 (a− d)(a+ d)= a − d < a .$ Попробуем рассмотреть геометрическую прогрессию, в которой $a$ и $a+ d$ — последовательные, а между $a$ и $a− d$ есть один член, тогда справедливо равенство $-a- a+d 2 a−d =( a ).$ После домножения на знаменатели, привидения подобных и деления на $d$ мы получим равенство $2 a = d(a+d).$ Чтобы свести его к уравнению от одной переменной, положим $a =kd$ , тогда оно примет вид $2 k = k+1.$ Это уравнение имеет корень $√5+1 k= 2 .$ Осталось заметить, что числа $√5−1 √5+1 √5+3 2 d, 2 d, 2 d$ при положительном $d$ подходят к условию.

Ответ: могут

Критерии оценки

+ верное решение

± верное решение с небольшими недочётами (например, арифметическая ошибка, не влияющая на ход решения)

+/2 задача явно сведена к решению полиномиального уравнения третьей степени или выше от знаменателя геометрической прогрессии, но не доказано (или доказано неверно) существование отличного от 1 решения

-. приведено доказательство невозможности в случае рациональных чисел или последовательных членов геометрической прогрессии

- решение не соответствует ни одному из критериев выше