Высшая проба 2022

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

Задумаемся, а существует ли такое Условие равносильно квадратному уравнению в остатках(в этом абзаце все сравнимости по модулю 7):

Или можно было просто перебором остатков, благо их всего 7, убедиться, что любой из 3 и 5 подходят.

Что же нам дает равенство Просится от обоих частей взять функцию а затем воспользоваться условием задачи. Имеем:

Чтобы подчеркнуть полученное, обозначим и выбросим среднюю часть:

Отсюда следует (далее все сравнимости будут по модулю 11)

Отметим что это именно следствие, а не равносильность. Выясним, имеет ли сравнимость решения, действуя стандартно А извлекается ли квадратный корень из -3 по модулю 11? Заметим что и Мы перебрали все остатки, среди квадратов не нашлось -3, значит корень не извлекается, значит уравнение не имеет решений.

Итак, требуемой функции не существует.

Заполним табличку: в клетке запишем, на какое максимальное число Вася может гарантированно к концу игры умножить имеющуюся у него сейчас сумму, если сейчас в ящике осталось черных и красных шаров. Легко понять, что стоит с краю: если уже не осталось черных шаров, то Вася может смело ставить все деньги на красный шар, соответственно увеличивая капитал в раз за каждый из оставшихся красных шаров. Аналогично если не осталось красных. Это и отмечено в таблице ниже.

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

Во-первых, в оптимальной стратегии Вася не должен делать положительные ставки на оба исхода. В самом деле, пусть по своей стратегии он должен сейчас поставить суммы и причем Тогда пусть вместо этого он поставит денег на тот исход, на который должен был ставить и на больше денег оставит не поставленными. Тогда при любом исходе он будет иметь на денег больше, чем имел бы, если бы ставил и

Теперь поймём, сколько же Вася должен ставить. Ставить он должен на тот цвет, выпадание которого приводит в клетку с числом напомним, в противном случае если этот цвет выпадет, Вася не сможет увеличить свой капитал более чем в раз, а мы строим стратегию лучше. Для определенности обозначим количество Васиных денег через и пусть он поставит денег на цвет, выпадение которого приводит в клетку с числом Тогда если выпал этот цвет Вася оказался в этой клетке имея денег, соответственно закончит игру, имея не менее денег (и не может гарантированно иметь больше). Если же выпал цвет, приводящий в клетку с числом Вася попал туда, имея денег, значит закончит игру, имея не меньше денег (и не может гарантированно иметь больше). Итак, гарантированный минимум при этой стратегии есть Поскольку первая из функций под минимумом возрастающая по , а вторая — убывающая, максимум минимума достигается при значении для которого функции принимают одно значение. Имеем

То есть

Иными словами, в интересующей нас клетке должно стоять число

Пользуясь этой формулой и значениями в клетках на краях, заполним всю табличку:

Введём обозначения для длин сторон:

Сделаем инверсию с центром и радиусом с симметрией относительно биссектрисы угла

Середины сторон прямоугольного треугольника и вершина его прямого угла образуют прямоугольник, значит, все четыре на одной окружности. Значит, при инверсии образ окружности — прямая. Легко посчитать, что эта прямая отсекает от лучей и отрезки длины и соответственно, то есть симметрична относительно биссектрисы угла Поэтому гипотенуза и окружность Эйлера треугольника переходят друг в друга.

Касательная из к вписанной окружности равна её радиусу а касательная из к вневписанной окружности равна полупериметру Таким образом, их произведение — площади треугольника Итак, Поэтому вписанная и вневписанная окружности треугольника переходят друг в друга.

Следовательно, переходит в а переходит в Угол переходит в угол значит, они равны.

Сразу заметим, что при равенство из условия невозможно, так что далее мы везде считаем, что даже когда не напоминаем об этом явно.

Предположим, что такие многочлены и нашлись. Тогда можно считать, что они взаимнопросты (иначе поделим оба на общий множитель — новая пара тоже удовлетворяет условию), и у старший коэффициент равен 1 (домножим и на константу , чтобы старший коэффициент стал равен 1). Введем обозначение для разложения на линейные множители (естественно, воспользовавшись существованием такого разложения в комплексных числах):

Для комплексного числа множество чисел вида где , будем называть цепью числа

______________________________________________________________________________________________________________________________________________________

Ключевое утверждение:

Если — корень то числа 0 и 1 принадлежат цепи

______________________________________________________________________________________________________________________________________________________

Доказательство.

Пусть — корень тогда обозначим через и такие минимальное и максимальное значения при которых является корнем Заметим, что и определены корректно: множество значений не пусто (поскольку 0 подходит) и конечно, поскольку у конечное число корней (первое место, в котором важно, что ). Тогда пусть не оба числа 0 и 1 лежат в цепи Тогда одно из двух чисел и не является ни 0 ни 1 (второе место: нам важно, что и — два разных числа). Рассмотрим эти два случая.

Пусть — не равно ни 0 ни 1. Посмотрим на равенство из условия

и разложим левую часть на простейшие дроби:

где степень меньше при причем

Поскольку — корень в разложение входит член со знаменателем и ненулевым числителем. Но — не корень иначе было бы корнем что противоречило бы максимальности . Тогда член со знаменателем не входит в разложение значит члену с таким знаменателем слева не с чем сократиться — но он не входит в правую часть — противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

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

Осталось показать, что все значения вида где подходят. Для достаточно взять функцию

и привести сумму к общему знаменателю, числитель взять в качестве а знаменатель — Для то же самое сделать с суммой

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

Для краткости точку будем обозначать просто Заметим, что точки не повторяются: если бы оказалось, что при то выполнялось бы и т.д., тогда число хорд было бы конечным. Итак, каждая новая точка попадает строго между ранее поставленными.

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

Теперь предположим, что мы уже индукцией по доказали, что все точки попадают на активную дугу -го шага при Определим активную дугу -го шага. лежит на -й активной дуге, значит делит ее на две части. На одну из этих частей попадает точка — эту часть и будем называть активной дугой -го шага. Тогда чтобы индукция работала нам осталось доказать, что все точки лежат на этой дуге при Понятно, что концы дуги — это какие-то из предыдущих точек значит есть фрагмент ломанной, соединяющий их. Значит если еще лежит на дуге, а — уже нет, и не совпадает ни с одной из предыдущих точек (что упоминалось ранее) — значит, пересекается с указанным фрагментом ломанной.

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

(1)

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

Если предел равен нулю, то нулю же равен и предел последовательности поскольку Но заметим, что То есть если то Кроме того, всегда не равно нулю (иначе две точки совпали). Значит для в последовательности встречаются члены большие со сколь угодно большими номерами — ноль не является пределом.

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

Выберем будем говорить о числах 0 и как о двух пределах. Начиная с какого-то номера все должны попадать в -окрестность одного из двух пределов. Но тогда при переходе от к расстояние до предела будет расти в 2022 раза - рано или поздно выскочит из -окрестности текущего предела и еще не дотянется до -окрестности другого предела.

Докажем оценку

______________________________________________________________________________________________________________________________________________________

Пусть существует стратегия, позволяющая ошибаться не более чем в битах т.е. Тогда заметим, что Наблюдатель, знающий стратегию Фокусника, сообщенное Ассистентом слово, и набор бит, в которых ошибся Фокусник, может восстановить написанное Зрителем слово. В самом деле, Наблюдатель берет слово, которое должен был написать Фокусник, и меняет его в тех местах, где Фокусник ошибся. Значит, количество различных пар вида "слово сообщенное Ассистентом и набор мест, в которых фокусник ошибся"не меньше, чем различных слов, которые мог написать зритель. То есть

Перепишем в виде

Заметим, что при неравенство неверно:

_________________________________________________________________________________________________________________________________________________________________________________

Теперь попробуем показать, из каких соображений строится пример. Для начала напомним конструкцию, известную как математикам так и программистам: двоичный код длины 15, позволяющий передать 11 бит полезной информации и исправить ошибку не более чем в одном бите (также известен как 15-битный код Хэмминга). Построим его.

Для начала заметим, что есть ровно 11 слов длины 4 из нулей и единиц, содержащих хотя бы две единицы (всего слов минус одно из одних нулей, минус четыре с одной единицей). Припишем такие слова номерам от 1 до 11 как угодно, например как в таблице:

Теперь построим код таким образом: в первые 11 бит запишем те биты, которые хотим передать (первые 11 позиций будем называть информационными). В последние 4 бита запишем следующие контрольные суммы. В 12-й запишем сумму по модулю два тех из первых 11 бит, приписанное 4-значное число которых имеет 1 в первом разряде, то есть биты № 3,5,6,8,9,10,11. В 13-й — сумму тех из первых 11 бит, приписанное 4-значное число которых имеет 1 во втором разряде, в 14-й сумму бит, имеющих 1 в третьем разряде приписанного слова, в 15-й — в четвертом. Покажем, почему этот код позволяет исправить одну ошибку при передаче.

_________________________________________________________________________________________________________________________________________________________________________________

Пусть Получатель получил кодовое слово, возможно искаженное в одном бите. Получатель точно так же по первым 11 битам посчитает 4 контрольные суммы, и сравнит их с четырьмя полученными. Если совпали все четыре — то слово дошло без искажений. В самом деле, если бы исказился контрольный бит — в нем было бы расхождение, а если информационный — то расхождения были бы во всех контрольных, в которые он входит. Аналогично, если расхождение есть ровно в одном контрольном бите, то исказился именно он. В самом деле, если исказился другой контрольный — то все информационные дошли правильно, тогда в этом контрольном расхождения бы не было; а если исказился информационный, то все контрольные дошли правильно, и тогда расхождения были бы во всех контрольных, в которые входит искаженный информационный, а таких контрольных хотя бы два (именно за этим мы приписывали комбинации нулей и единиц, содержащие хотя бы две единицы). По аналогичным соображениям если получатель видит не менее двух расхождений с контрольными битами, то искажен точно информационный. Тогда достаточно из 11 информационных позиций выбрать ту, в приписанном 4-битном слове которой единицы стоят ровно на тех местах, на которых есть расхождения с контрольными суммами — это и есть искаженная позиция.

_________________________________________________________________________________________________________________________________________________________________________________

Теперь подумаем в других терминах, что же мы построили. У нас есть код из кодовых слов. Каждое из этих слов можно исказить 16 способами (ничего не менять, или изменить один из 15 бит). Все полученных в результате слов будут разными. В самом деле, если бы какое-то слово получалось двумя разными способами: искажением кодового слова и искажением кодового слова (в обоих случаях — не более чем в одном бите), то код бы не исправлял одну ошибку — Получатель может получить слово но в этом случае не может понять, посылали ему или Итак, все слов разные, но это означает что вообще любое из слов длины 15 получается искажением какого-то из кодовых слов не более чем в одном бите.

На этом и построим стратегию Фокусника и Ассистента. Ассистент видит написанное зрителем 60-битное слово, режет его на четыре 15-битных слова Как доказано выше, для них найдутся кодовые слова такие что отличается от не более чем в одном символе. Тогда Ассистент выбрасывает из каждого кодового слова контрольные символы, получает четыре слова длины 11, то есть одно слово длины 44. Его он и передает Фокуснику. Фокусник восстанавливает контрольные суммы, получает слово отличающееся от исходного максимум в четырех битах — победа.