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

Алгебраические текстовые задачи на Высшей пробе

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

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

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

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

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

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

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

Задача 1#74782

Через $X (α)$ будем обозначать точку с координатами $(cosα,sinα )$ (все такие лежат на окружности радиуса 1 с центром в начале координат). Выбрали произвольный угол $ϕ$ и провели хорды $( 2 ) P (ϕ)P(2022ϕ),P(2022ϕ)P 2022ϕ ,...$ (на шаге номер $n$ проводится хорда $( n−1) n ) P 2022 ϕ P (2022 ϕ).$ Если хорда уже была проведена — она не проводится второй раз. Оказалось. что все проведенные хорды не пересекаются иначе чем по концам. Докажите, что всего проведено конечное число хорд.

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

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

Подсказка 1

Давайте введем функцию, выражающую расстояние между двумя точками на окружности.

Подсказка 2

Обозначим целую часть числа x за {x} и введем функцию <x>. При {x} ≤ 1/2: <x> = {x}. При {x} > 1/2: <x> = 1 - {x}. Тогда, например, если длина дуги между точками a и b равна φ, то длина дуги между 2022a и 2022b равна <2022φ>. Теперь подумайте, какому условию должны удовлетворять наши точки.

Подсказка 3

Для краткости будем обозначать точку P(2022ⁿφ) за Pₙ. Заметьте, что точки не могут повторяться.

Подсказка 4

Действительно, если m > n и Pₘ = Pₙ, то выполнялось бы Pₘ₊₁ = Pₙ₊₁, Pₘ₊₂ = Pₙ₊₂ и т.д.. Получилось бы, что число хорд — конечно. Поэтому будет считать, что каждая новая точка попадает строго между ранее поставленными.

Подсказка 5

Введем понятие активной дуги n-го шага. Для натурального n = 1 будем ей считать ту из двух дуг P₀P₁, на которую попадает P₂. Заметьте, что тогда все точки Pₙ лежат на активной дуге первого шага.

Подсказка 6

Действительно, пусть все точки от 2 до m лежат на активной дуге первого шага, а (m + 1)-я — не лежит. Тогда хорды P₀P₁ и PₘPₘ₊₁ пересекаются. Теперь предположим, что мы индукцией по n доказали, что все точки Pₘ попадают на активную дугу n-го шага при m > n. Попробуйте определить активную дугу (n + 1)-го шага.

Подсказка 7

Pₙ₊₁ лежит на n-ой активной дуге, значит, делит ее на 2 части. На одну из этих частей попадает точка Pₙ₊₂ — эту часть и будем называть активной дугой (n + 1)-го шага. Что нам осталось для того, чтобы индукция сработала?

Подсказка 8

Все точки Pₘ должны лежать на этой дуге при m ≥ n + 2.

Подсказка 9

Концы дуги - это какие-то из предыдущих точек P, следовательно, есть фрагмент ломаной, соединяющий их. Какой вывод можно сделать?

Подсказка 10

Если Pₘ еще лежит на дуге, а Pₘ₊₁ — уже нет, и Pₘ₊₂ не совпадает ни с одной из предыдущих точек P, то PₘPₘ₊₁ пересекается с указанным фрагментом ломаной. А что можно сказать про отношение между активными дугами?

Подсказка 11

Каждая следующая активная дуга является подмножеством предыдущей. Давайте обозначим через φₙ длину активной дуги, а через ψₙ — длину дуги Pₙ₋₁Pₙ (той, которая лежит внутри активной). Что можно сказать про отношение этих величин?

Подсказка 12

Или φₙ = ψₙ, или φₙ = φₙ₋₁ - ψₙ. Что можно сказать о последовательности {φₙ}?

Подсказка 13

Это невозрастающая последовательность положительных чисел, следовательно, имеет предел. Докажите, что это невозможно. Что если, например, предел равен нулю?

Подсказка 14

Тогда нулю будет равен и предел {ψₙ}, так как ψₙ ≤ φₙ₋₁. Заметьте, что ψₙ₊₁ = <2022ψₙ>.

Подсказка 15

Если ψₙ ≤ 1/4044, то ψₙ₊₁ = 2022ψₙ. Кроме того, ψₙ всегда не равно нулю. Почему?

Подсказка 16

Потому что иначе две точки бы совпали. Какой ε можно выбрать, чтобы доказать, что 0 не является пределом?

Подсказка 17

Если ε = 1/4044, то в последовательности встречаются члены, большие ε, со сколь угодно большими номерами. Теперь предположим, что предел равен положительному числу а.

Подсказка 18

Так как φₙ равно ψₙ или φₙ₋₁ - ψₙ, последовательность ψₙ разбивается на две подпоследовательности. Чему равны их пределы?

Подсказка 19

Их пределами будут 0 и a. Кроме того, по доказанному ранее, вторая (у которой предел — a) будет иметь бесконечное число членов.

Подсказка 20

Попробуйте рассмотреть некоторое преобразование (в нем используется <x>) и сделать вывод о точке а.

Подсказка 21

Для преобразования ψ → <2022ψₙ> a будет неподвижной точкой. Запишите отношение между a, ψₙ и ψₙ₊₁.

Подсказка 22

Если |ψₙ - a| ≤ 1/4044, то |ψₙ₊₁ - a| = 2022|ψₙ - a|. Будем думать о 0 и a как о двух пределах. Надо вновь подобрать ε.

Подсказка 23

Что, если взять ε < a/2022?

Подсказка 24

Начиная с некоторого номера, ψₙ должны будут попадать в ε-окрестность одного из пределов. А что случится при переходе от ψₙ к ψₙ₊₁?

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

Нам будет полезен аналог целой части $< x> ,$ выражающий для двух чисел с разностью $x$ расстояние по окружности между образами этих чисел, если намотать числовую прямую на единичную окружность: будем говорить, что $<x >= {x}$ при $1 {x}≤ 2$ и $< x>= 1 − {x}$ при $1 {x}> 2$ (здесь ${x}$ обозначает обычную целую часть числа $x$ ). Тогда, например, если длина дуги между точками $α$ и $β$ равна $ϕ,$ то длина дуги между $2022α$ и $2022β$ равна $< 2022ϕ> .$

Для краткости точку $n P(2022ϕ)$ будем обозначать просто $Pn.$ Заметим, что точки не повторяются: если бы оказалось, что $Pm =Pn$ при $m > n,$ то выполнялось бы $Pm+1 = Pn+1,$ $Pm+2 =Pn+2$ и т.д., тогда число хорд было бы конечным. Итак, каждая новая точка попадает строго между ранее поставленными.

Определим по индукции понятие активной дуги $n$ -го шага. Для натурального $n = 1$ будем ей считать ту из двух дуг $P0P1,$ на которую попадает $P2$ . Заметим, что тогда все точки $Pn$ лежат на активной дуге первого шага. В самом деле, пусть все точки от 2 -й до $m$ -й лежат на активной дуге 1 -го шага, а $m +1$ -я там не лежит. Тогда хорды $P0P1$ и $PmPm+1$ пересекаются.

Теперь предположим, что мы уже индукцией по $n$ доказали, что все точки $Pm$ попадают на активную дугу $n$ -го шага при $m >n.$ Определим активную дугу $n+ 1$ -го шага. $Pn+1$ лежит на $n$ -й активной дуге, значит, делит ее на две части. На одну из этих частей попадает точка $Pn+2$ — эту часть и будем называть активной дугой $n+ 1$ -го шага. Тогда чтобы индукция работала нам осталось доказать, что все точки $Pm$ лежат на этой дуге при $m ≥n +2.$ Понятно, что концы дуги — это какие-то из предыдущих точек $P,$ значит есть фрагмент ломанной, соединяющий их. Значит, если $Pm$ еще лежит на дуге, а $Pm+1$ — уже нет, и $Pm+2$ не совпадает ни с одной из предыдущих точек $P$ (что упоминалось ранее) — значит, $PmPm+1$ пересекается с указанным фрагментом ломаной.

Как легко видеть, каждая следующая активная дуга является подмножеством предыдущей. Более того, обозначим через $ϕn$ длину активной дуги, а через $ψn$ — длину дуги $Pn−1Pn$ (той из двух, которая лежит внутри активной). Тогда или

ϕn = ψn или ϕn =ϕn−1− ψn

(1)

Поскольку ${ϕ }∞ n n=1$ — невозрастающая последовательность положительных чисел, она имеет предел. Докажем, что этого не может быть.

Если предел равен нулю, то нулю же равен и предел последовательности $∞ {ψn}n=1,$ поскольку $ψn ≤ϕn−1.$ Но заметим, что $ψn+1 =<2022ψn > .$ То есть если $-1- ψn ≤ 4044,$ то $ψn+1 =2022ψn.$ Кроме того, $ψn$ всегда не равно нулю (иначе две точки совпали). Значит, для $-1- 𝜀= 4044$ в последовательности встречаются члены, большие $𝜀,$ со сколь угодно большими номерами — ноль не является пределом.

Пусть предел равен положительному числу $a.$ Тогда по $(1)$ последовательность $ψn$ разбилась на две подпоследовательности, предел одной равен нулю, предел другой — $a$ , причем, по доказанному выше, вторая содержит бесконечное число членов. Заметим, что $a$ — неподвижная точка преобразования $ψ →< 2022ψn >.$ Тогда аналогично $|ψn+1− a|=2022|ψn − a|$ если $1 |ψn− a|≤ 4044.$

Выберем $𝜀< 20a22,$ будем говорить о числах 0 и $a$ как о двух пределах. Начиная с какого-то номера все $ψn$ должны попадать в $𝜀$ -окрестность одного из двух пределов. Но тогда при переходе от $ψn$ к $ψn+1$ расстояние до предела будет расти в 2022 раза - рано или поздно $ψn$ выскочит из $𝜀$ -окрестности текущего предела и еще не дотянется до $𝜀$ -окрестности другого предела.

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

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

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

Задача 2#121822

Дано несколько вещественных чисел, по модулю не превосходящих $1.$ Сумма всех чисел равна $S.$ Докажите, что из них можно выбрать несколько чисел так, чтобы при некотором натуральном $n <100$ сумма выбранных чисел отличалась от $nS- 100$ не более чем на $-1- 100.$

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

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

Подсказка 1

Обозначим данные k чисел за x₁, x₂, ... , x_k. Давайте, например, поймем, что нам дает условие на модуль.

Подсказка 2

Можно без ограничения общности считать, что сумма чисел у нас положительная. Хорошо, нас просят выбрать несколько чисел, а какие это могут быть числа? Важен ли нам их порядок?

Подсказка 3

Нам ведь могут от примера к примеру мешать числа, как угодно, давайте тогда для удобства рассматривать подряд идущие. Как можно переформулировать условие задачи? Какие числа мы ищем?

Подсказка 5

У нас n - натуральное, давайте рассмотрим наименьшие индексы m_1, m_2, ... , m_99, такие, что x₁ + x₂ + ... + xₘ_₁ ≥ S/100, x₁ + x₂ + ... + xₘ_₂ ≥ 2*S/100 и так далее. Как они могут нам помочь в оценке? Может, нам чего-то еще не хватает? Вспомните, что мы хотим доказать.

Подсказка 6

Доопределим разность суммы каждой последовательности и соответствующей ей оценки: aᵢ = x₁ + x₂ + ... + xᵢ - i*S/100. Кстати, все ли они определены? А можем ли мы как-то оценить величину каждой aᵢ?

Подсказка 7

mᵢ и aᵢ определены, так как по крайней мере для k при любом i выполняется x₁ + x₂ + ... + x_k = S ≥ i*S/100. Давайте формально доопределим m₀ = 0 и a₀ = 0. Выбранные нами индексы были первыми для своего условия, а также все xᵢ по модулю не превосходят 1, следовательно, значения aᵢ лежат в отрезке [0;1]. А можем ли мы сжать этот отрезок для удобства и попробовать оценить разницу между какими-нибудь aᵢ и aⱼ, где i ≠ j? Какое неравенство мы хотим получить по условию задачи?

Подсказка 8

Преобразуйте неравенство и подумайте, какое n можно взять, чтобы получившаяся последовательность была искомой.

Подсказка 9

Несколько ранее мы предположили, что отрезок величин aᵢ можно сжать для получения искомой оценки, а если для некоторого i a_i попадает в отрезанный кусок? Какое множество чисел может быть искомым?

Подсказка 10

Подумайте, как доказать, что в таком случае набор чисел x₁, x₂, ... , x_(m_i-1) нам подойдет.

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

Обозначим данные $k$ чисел через $x,x ,...,x . 1 2 k$ Без ограничения общности будем считать, что $S ≥ 0.$ Если это не так, то будем доказывать утверждение задачи для чисел $yi = −xi$ с положительной суммой. Из него будет следовать утверждение исходной задачи.

Докажем, что среди данных чисел существует набор из подряд идущих, удовлетворяющих неравенству из условия. То есть найдутся такие натуральные $s$ и $t$ $(1≤ s≤ t≤k),$ что подмножество $xs,xs+1,...,xt$ — искомое.

Обозначим через $m1$ первый индекс, для которого

S x1+x2+ ...+ xm1 ≥ 100,

через $m2$ — первый индекс, для которого

x1+x2+ ...+ xm2 ≥-2S-, 100

и так далее:

x1+ x2+...+xmi ≥-iS- 100

по всем $i$ от $1$ до $99.$ Рассмотрим также разности

a = x +x +...+ x − -iS- i 1 2 mi 100

Заметим, что $m i$ и $a i$ определены, поскольку по крайней мере для $k$ выполняется неравенство

x1+ x2 +...+ xk = S ≥-iS- 100

для любого $i.$ Формально доопределим: $m0 = 0$ и $a0 = 0.$ Заметим теперь, что так как выбранные нами индексы были первыми для своего условия и так как все числа $xi$ по модулю не превосходят $1,$ то все $ai$ лежат на отрезке $[0;1].$

Предположим, все $ai$ лежат на отрезке $[0;1− 1100].$ Тогда, так как чисел $ai$ всего $100$ (для $i$ от $0$ до $99),$ найдутся два индекса $i$ и $j,$ для которых $|ai− aj|≤ -1. 100$ Без ограничения общности $j >i.$ Тогда $mj ≥ mi$ по определению чисел $mi.$ Получаем:

| | ||(x + x + ...+ x )− (x +x + ...+ x )+ jS-− iS||≤ -1- | 1 2 mi 1 2 mj 100 100| 100

или, что то же самое,

|| (j− i)S|| 1 ||xmi +xmi+1+ ...+ xmj −--100--||≤ 100.

Заметим, что можно взять $n =j− i,$ поскольку $j− i> 0$ и $j− i≤ j <100.$ Тем самым, числа $xmi,xmi+1,...,xmj$ — искомые.

Пусть теперь для некоторого $i$ разность $ai$ попала на полуинтервал $(1 −1100,1].$ Докажем, что в этом случае подмножество $x1,...,xmi−1$ — искомое. Для этого достаточно показать, что

iS-− -1-< x1 +...+xmi−1 ≤-iS-. 100 100 100

Второе неравенство следует из определения $mi;$ ведь $mi$ — это первый индекс, для которого сумма стала не меньше $-iS-. 100$ Первое неравенство равносильно следующему: $x1+...+xmi−1− iS-> −-1. 100 100$ Но