Сложный вариант весеннего тура Турнира Городов

Первое решение.

Рассмотрим всевозможные мелодии из нот до и си длины , коих штук. Каждую такую мелодию периодически продолжим в обе стороны, получив бесконечную в обе сторону мелодию. Назовём две получившиеся бесконечные мелодии эквивалентными, если одна получается из другой сдвигом.

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

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

Из них мелодий, содержащих запрещённые Кощеем мелодии, не больше

(в скобках учтены запретные мелодии длины , полученные дописыванием символов к запретной мелодии длины , а за скобками — все остальные).

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

______________________________________________________________________________________________________________________________________________________

Второе решение.

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

База индукции

Предположим, что неравенство верно для всех , меньших Покажем, что тогда Заметим, что

Действительно, мы можем добавить в конец ноту двумя способами к уже имеющейся незапрещенной мелодии из нот. При добавлении ноты могла возникнуть запретная мелодия длины в конце последовательности, однако она "испортит"максимум последовательности нот, так как первые ноты до "запрещенной"мелодии - незапрещенная мелодия длины . Аналогично могли получить запретную последовательность из нот и испортить разрешённую мелодию из нот и т. д. (Здесь мы можем вычесть лишнее, если , и часть вычитаемых мелодий могут быть одинаковыми, но поскольку мы пишем оценку снизу, всё правильно.)

Из предположения индукции для также следуют неравенства:

Применим эти следствия, а также неравенство выше, для доказательства перехода индукции и получим:

Следовательно, и переход доказан.

Тогда из-за положительности последовательность возрастающая, а значит , откуда следует, что Иван справится с испытанием Кощея.

Заметим, что и — средние линии треугольников и поэтому и Тогда

По свойству касательной и секущей к окружности имеем откуда

Аналогично получаем

Деля одно на другое и пользуясь тем, что находим

Получаем, что треугольники и подобны по углу и отношению прилежащих сторон.

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

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

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

Установим взаимно-однозначное соответствие между словами Пети и Васи. Разобьём Васино слово из букв на блоки из двух букв. Заменим каждый блок на букву блок — на букву блок — на букву и блок — на букву Получится слово из букв, в котором букв и поровну (изначально их было поровну, замена блоков и убирает равное число букв и а значит, и блоков будет столько же, сколько блоков ). Итак, каждому слову Васи мы сопоставили слово Пети.

Наоборот, по каждому -буквенному слову Пети легко восстановить, из какого слова Васи оно получилось по описанному выше правилу: надо заменить буквы по тому же правилу.

Пусть — точка пересечения прямых и — точка касания окружностей и Рассмотрим композицию инверсии с центром в точке радиусом

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

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

Осталось заметить, что следовательно, совпадает с аналогично, совпадает с

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

Рассмотрим ту из стёртых диагоналей, которая отсекала наименьшее число вершин. Внутри отсечённого ею многоугольника диагоналей не проводилось, значит, отсечён треугольник, и у вершины против диагонали написана единица.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Решим более общую задачу: пусть учеников занимаются в кружках (из трёх человек), Предположим противное: каждые два кружка либо не пересекаются, либо пересекаются ровно по двум ученикам. Заметим, что если кружки и пересекаются с кружком M, то они пересекаются и между собой (их пересечения с имеют общий элемент). Значит, кружки разбиваются на группы пересекающихся между собой кружков. Каждой группе кружков соответствует группа учеников — объединение их составов. Эти группы также не пересекаются. Далее можно рассуждать по-разному.

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

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

Итак, число кружков не превосходит числа учеников в классе.