Высшая проба - задания по годам → .08 Высшая проба 2022

Подсказка 1

Такс, перед нами функциональное уравнение, да еще и аргумент функции мы берем по модулю 7… Давайте вспомним, что мы обычно делаем в функциональных уравнениях?

Подсказка 2

Верно, подставляем хорошие значения! А какие значения хочется подставить в это уравнение(не забывайте, что в левой части аргумент берется по модулю)

Подсказка 3

Да, хочется найти такие x, для которых верно: x = x²+1 по модулю 7. Почему так хочется сделать? Если получится найти такой x, то дальше уравнение сведется к f(x) = (f(x)²+1) (по модулю 11). А понять, решается ли такое уравнение уже проще, чем решить исходное! Остаётся найти такие x.

Подсказка 4

Заметим, что 3 = 3²+1 по модулю 7! То есть, 3 нам подходит. Что можно сказать про f(3)?

Подсказка 5

Верно, f(3) = f(3)²+1 по модулю 11. Мы получили почти то же самое, что и на одном из предыдущих шагов, только теперь по модулю 11! Остаётся показать, что таких y не существует.

Подсказка 1

Мы понимаем, что у нас в задаче Вася может максимум 6 раз сделать ставку. Тогда имеет смысл "перебрать случаи". Давайте будем заполнять табличку 4 на 4(0, 1, 2 и 3 красных шара по вертикали и аналогично для чёрных по горизонтали), которая будет говорить о том, во сколько раз увеличится выигрыш, когда осталось определённое число шаров. Тогда во сколько раз увеличатся деньги, после того как у нас останутся шары только одного цвета?

Подсказка 2

Верно, они могут увеличиваться в p, p^2, p^3 раз. Вася будет просто ставить всю сумму каждый раз на один цвет. Это то, что будет стоять в крайних столбцах и диагоналях. Ещё понятно, если шаров нет, то мы ничего не выигрываем, то есть 1 коэффициент в клетке (0; 0). Давайте поймём такую вещь, а есть ли Васе смысл ставить деньги на оба шара?

Подсказка 3

Да, смысла в этом нет, Васе надо ставить какую-то часть денег только на один цвет. Если он поставит a денег на один цвет, а b на другой, то получит на 2(p-b) денег меньше, чем если бы поставил a-b на один цвет. Это несложно посчитать. Теперь давайте попробуем разобраться с другими клетками. Например, если остался 1 чёрный и 1 красный шарик. Во сколько раз мы получим больше денег точно? Полезно будет ввести неизвестные.

Подсказка 4

Верно, мы получим больше в p раз. Дело в том, что даже если мы не угадаем шар, то следующим ходом увеличим в p раз количество денег. Давайте теперь попробуем в общем виде провести рассуждения. Если у Васи было X денег, а поставил он aX, где a какое-то число от 0 до 1. Значит, мы можем посчитать случаи, когда Вася угадал и когда не угадал. Но тогда сколько гарантированно он получит? Что это может значить с точки зрения полученных формул?

Подсказка 5

Да, гарантированный выигрыш — это минимум из двух наших выражений. Но можно заметить, что одно из них убывающее, а другое возрастающее от a. Значит, и минимум будет, когда они равны. Отсюда мы получаем a, а потом и во сколько раз увеличится наше количество денег. Так мы, постепенно заполняя таблицу, получим, что должно быть в клетке, где 3 шара каждого цвета. Это и будет ответ на задачу, победа!

Подсказка 1

Понятно, что скорее всего стандартный счёт углов тут не поможет. Здесь у нас и окружность Эйлера, и вписанная, и вневписанная. Так что либо нужны большие знания геометрических конструкций, либо какие-то хитрости. Пойдём хитрым путём. У нас есть как минимум три окружности на картинке, причём какие-то касающиеся. Какое преобразование плоскости тогда напрашивается сделать?

Подсказка 2

Верно, давайте сделаем инверсию с центром в точке C, причём сделать её с произвольным радиусом не слишком удобно. Давайте сделаем инверсию с радиусом √(ab/2), где переменные это стандартное обозначение сторон. Но если вы начнёте рисовать новую картинку, выйдет что-то не слишком хорошее. Какое ещё преобразование плоскости хорошо будет применить?

Подсказка 3

Смотрите, а давайте после инверсии сделаем ещё симметрию. Вот теперь осталось только понять, что и куда переходит после преобразований окончательно и почему мы выбрали такой радиус инверсии(на самом деле можно было без него, но так удобнее). В конце концов мы поймём, что углы переходят в друг друга, и победа!

Подсказка 1

Мы знаем, что 1/x(x+ 1) = 1/x - 1/(x + 1) - так мы удобно для себя разложили правую дробь. Однако, мы знаем, что любую, так называемую иррациональную дробь (то есть, где сверху и снизу - многочлены) можно разложить на сумму вида P_i(x) / (x - alpha_i) ^ n_i, где P_i(x) - не нулевой многочлен, а alpha_i - корень, возможно комплексный(чтобы было линейно разложимо) многочлена Q(x). Поэтому основная идея задачи - разложить дроби в такой вид и смотреть на то, могут ли как-то сократиться подобные. То есть, если у вас есть к примеру, в левой часть какой-то не сократившийся член 1/(x + k), а справа его нет, то это значит, что равенство происходит только в конечном числе точек, что нам не подходит. В правой часть у нас только 1/x - 1/(x + 1), значит и в левой части должно быть также. Значит, по нашему предположению о решении задачи - хотелось бы доказать, что-то насчет 0,1 и их связи с корнями. Если мы хотим доказывать от противоречия и как-то использовать корни, то, с учетом вот этой «несократимости», которая была описана выше, как мы хотим его получить?

Подсказка 2

Удачным был бы шаг решения, когда мы получили какой-то корень отличный от 0 и 1, при этом, такой, чтобы он был корнем Q(x), но не корнем Q(x + d), потому что тогда бы мы получили бы в нашем разложении на сумму дробей что-то, что не сокращается с Q(x + d) и не сокращается с правой частью. И поскольку мы каждый раз прибавляем x + d (напомним - мы можем подставлять почти, с точностью до конечного числа, любые значения и будет выполнено равенство), то наверное правильным решением будет ввести понятие цепи - всевозможных чисел вида alpha + md, где m - целое и alpha - корень Q(x). А также нам надо что-то понимать про то, какие из чисел этой цепи являются корнем или нет. Попробуйте использовать принцип крайнего и получите хорошее утверждение, которое значит больше половины задачи.

Подсказка 3

Нам удобно ввести m_- и m_+ - наименьшее и наибольшее соотвественно число, при котором alpha + md является корнем Q(x) (корректно ли это определение?). Тогда в смысле цепи нам бы хотелось доказать, что если alpha - корень, то 0 и 1 лежат в цепи alpha. Предположим, что хотя бы одно не лежит в цепи. Тогда, корень Q(x) - alpha_i = alpha + m_+ * d не равно ни 0, ни 1. Может ли быть, что это также корень Q(x + d)? А о чем тогда это говорит в связи с предыдущими рассуждениями?

Подсказка 4

Конечно, это не может быть корнем Q(x + d), иначе тогда бы alpha + (m_+ + 1) * d был бы корнем Q(x), что противоречит максимальности. Тогда эта дробь, соответствующая корню, не сократится ни с Q(x + d), ни с правой частью. А потому пришли к противоречию. Значит, для некоторого целого m_1 верно, что alpha + m_1 * d = 0, и для некоторого целого m_2 верно, что m_2 * d + alpha = 1, а значит, (m_2 - m_1) * d = 0 = > для некоторого целого m выполнено, что md = 1 => d = 1/m, где m - целое. Осталось доказать, по хорошему, конструктивно, что все такие d подходят. Если строить пример, то надо строить его в виде уже разложенных в сумму дробей многочленов, потому что нам потом самим раскладывать. Какой тогда пример мы можем привести, если хотим, чтобы после разности очень похожих дробей (по сути - все сместится на 1/m в знаменателях и это будет что-то очень похожее), у нас осталось только 1/x - 1/(x + 1)? Может быть как то, условное «смещение» некоторой последовательности использовать? А как его добиться?

Подсказка 5

Если мы хотим добиться смещения по последовательности, то нам надо, чтобы при прибавлении 1/m для каждого члена у нас получался следующий, а также, чтобы последний член становился равным 1, чтобы получалось 1/(x + 1). На такую роль очень подходит дробь вида 1/x + 1/(x + 1/m) + 1/(x + 2/m) + … + 1/(x + (m - 1)/m). Тогда все работает. А правда ли, что этот пример работает для всех m? А если взять m = -1? К тому же, стоит, напоследок, перед тем как полностью решить задачу подумать, к чему тут именно конечное число точек, а не нулевое и везде ли мы делали корректные переходы не упуская случай d = 0. Пробегитесь по решению и проверьте на корректность все

Подсказка 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

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

Подсказка 1

Давайте начнём решать эту задачу с оценки. Причём мы будем рассуждать так, что фокусник при выписывании последовательности ошибся максимум в k символах, то есть C = 60 - k. Пусть мы знаем последовательность, написанную фокусником. Тогда с помощью какой информации на основе введённых данных мы сможем определить исходную последовательность?

Подсказка 2

Верно, нам нужно знать, в каких символах он ошибся. Тогда мы сможем однозначно определить последовательность. Но как нам это поможет в задаче? Давайте представим немного нашу задачу через множество и его покрытие. Всего возможных последовательностей, которые может написать зритель это 2^60. Давайте подумаем, как мы можем посчитать, сколько покроет одна последовательность, учитывая, что фокусник может ошибиться максимум в k знаках?

Подсказка 3

Верно, это считается с помощью числа сочетаний. Может быть такое, что он вовсе не ошибся, ошибся один раз и т.д. до максимум в k знаках. И того, для одной последовательности мы получаем сумму числа сочетаний. Но всего фокусник может получить 2^44 различных последовательностей, имея информацию от ассистента. Тогда учитывая мысль про покрытия множества размером 2^60, какую оценку мы получаем?

Подсказка 4

Да, сумма, умноженная на 2^44, должна быть больше 2^60. Но зачем? Чтобы даже, если мы ошибёмся максимум в k знаках, то мы всё равно победим, так как затронем все последовательности. Таким образом, несложной прикидкой получим оценку для k=4, откуда C=56. Теперь в следующей подсказке разберёмся с примером.

Подсказка 5

Суть нашего примера будет заключаться в том, как же действовать ассистенту, то есть какую последовательность передавать, и, что с ней делать фокуснику. Заметим, что фокусник в итоге ошибается только в 4 позициях. Давайте тогда для удобства, пока магически разобьём то, что будет передавать ассистент на блоки по 11 цифр. Тогда в каждом блоке фокусник будет что-то досчитывать, записывать и, в итоге, ошибаться максимум 1 раз в блоке. Попробуйте поугадывать, какая информация ему может понадобиться из этих 11 цифр? Стоит подумать в сторону информатики, последовательности 0 и 1 из 4 знаков и чётности, нечётности.

Подсказка 6

Давайте составим табличку из последовательностей с четырьмя символами, в которых есть хотя бы две единицы, и пронумеруем. Их будет как раз 11 штук. В последние 4 позиции блока запишем следующие "контрольные" суммы. Сначала запишем сумму по модулю два тех из первых 11 позиций, записанное 4-значное число которых имеет 1 в первом разряде. Потом аналогичное сделаем для 1 во втором разряде и т.д. до 4 разряда. Попробуем взять произвольную последовательность из 15 символов, а записать только 11. Посчитаем для них самостоятельно контрольные суммы. Теперь поизучайте эту конструкцию, например, что будет если контрольные суммы не совпадут? В скольких разрядах у них будет расхождение и где может быть ошибка – в четырех контрольных суммах или в первых 11 цифрах? А сколько в принципе может случится ошибок в такой строке, если не совпали контрольные суммы?

Подсказка 7

Ага, несложным перебором, где и сколько штук можно было допустить ошибок, понимаем, что она возможна только одна(либо в 11 цифрах, либо в контрольных суммах). Но для чего это всё таки было? Попробуйте прокрутить теперь эту конструкцию в обратном порядке. Пусть мы получили "кодовое слово" длины 15. Дальше считаем контрольные суммы по первым 11 цифрам и дописываем их. Таким образом, 15 цифр будут расходится максимум в 1 позиции. Как тогда отсюда получается окончательный пример?

Подсказка 8

Да, получается, что ассистент бьёт 60 цифр на группы по 15 и делает для них "кодовые слова" длинной 11, убирая контрольные суммы. Так и получается всего передача 44 знаков. Фокусник же далее восстанавливает контрольные суммы, как и само слово, ошибившись максимум 4 раза. Но всё таки осталось ещё понять, почему же вообще любое из слов длины 15 получается искажением какого-то из кодовых слов не более чем в одной позиции. И после этого будет победа!