Регион 11 класс

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

Теперь покажем, что такое дерево существует, для этого докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Есть 2 четвёрки чисел

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

Доказательство. Разберем несколько случаев:

Если не умаляя общности и можно сгруппировать

В случае и н.у.о. группируем

сводится к предыдущему, если мы перейдем к четверкам чисел

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Построив снизу вверх так первые уровня дерева, мы в итоге получим четверку различных чисел

далее рассмотрим вершины со значениями(и соответствующими потомками) и и последнем шаге сложим уже эти два числа, получив в корне.

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

Первый способ — сумма одинаковых дробей Построим три других представления. Заметим, что среди чисел

не более одной степени двойки и не более двух простых чисел (потому что простые числа, большие трех, могут давать только остатки 1 и 5 от деления на 6), уберем такие числа из рассмотрения. Любое оставшееся число можно представить в виде где и нечетно. Тогда кратно обозначим частное от деления через Получаем, что

Возьмем дроби вида и дроби вида Поскольку то

Посчитаем сумму этих дробей:

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

откуда и противоречие.

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

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

Пусть среди множеств

нашлись два множества и имеющие общих элементов

Для каждого элемента среди множеств

найдём подмножество не содержащее такое подмножество найдётся, иначе — общий элемент множеств

(Заметим, что среди подмножеств могут быть совпадающие.)

Тогда пересечение не более подмножеств

— пусто. Это противоречит нашему предположению (к данным подмножествам можно добавить еще несколько, чтобы стало 30 подмножеств, при таком добавлении пересечение остается пустым).

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

содержит в точности элементов. Пусть

так что

Найдём подмножество (пусть, для определённости, это подмножество — ), не содержащее Так как

то обязано содержать все элементы

Этих элементов (все они различны), поэтому

Рассмотрим любое подмножество из подмножеств Предположим, что содержит элемент, лежащий вне -элементного множества

Тогда должно пересекаться с каждым из подмножеств по одному и тому же -элементному подмножеству множества Но

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

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

также кратна из чего следует, что нечётно. Значит,

— чётное число, и нечётное число не может на него делиться.

Первое решение. Так как многочлен

имеет старший коэффициент и корни то

Подставим в последнее равенство вместо получим

что равносильно

Из полученного равенства получаем, что тремя корнями уравнения являются числа

______________________________________________________________________________________________________________________________________________________

Второе решение. По теореме Виета выполняются следующие соотношения:

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

из чего следует, что числа и являются корнями уравнения

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

Действительно, для пары число делится на 7.

Пусть для пары число делится на Тогда для пары число

делится на и для пары число

делится на

Пусть для пар числа делятся на 7. Тогда для пары число

делится на

Так как для пары число

не делится на эта пара на доске появиться не может.

_________________________________________________________________________________________________________________________________________________________________________________

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

______________________________________________________________________________________________________________________________________________________

Утверждение. Докажем, что все тройки, появляющиеся на доске, имеют вид

с целыми и В начальный момент времени это верно:

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

Утверждение доказано.

_________________________________________________________________________________________________________________________________________________________________________________

Предположим теперь, что на доске появилась тройка (2022, 2023, -4045), то есть она имеет вид Тогда имеем

Выражая из первого равенства и подставляя во второе, получаем

то есть

Однако это невозможно, поскольку не делится на

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

В самом деле, по теореме Менелая для треугольника и прямой имеем

Поскольку прямые и параллельны между собой (так как они все перпендикулярны прямой ), имеем

Значит,

из чего следует, что точки и лежат на одной прямой по теореме Менелая для треугольника Значит, точка диаметрально противоположна точке в окружности

Аналогично, если — точка пересечения перпендикуляра к прямой проходящего через точку и прямой то точка диаметрально противоположна точке Из этого следует, что и, аналогично,

Обозначим через и точки пересечения прямой соответственно с прямыми и Заметим, что треугольники и подобны как прямоугольные с вертикальными острыми углами. Значит, или

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

Возьмём прямоугольник размера половина площади которого равна Для того, чтобы условие выполнилось, из данного прямоугольника необходимо вырезать прямоугольники площади или Таких прямоугольников всего три: и Заметим, что длина стороны каждого из таких прямоугольников не меньше С другой стороны, диагональ исходного прямоугольника равна но

поэтому ни один из таких прямоугольников вырезать из прямоугольника нельзя.

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

как внешний к треугольнику Таким образом, поэтому точка лежит на окружности, описанной около треугольника

Рассуждая аналогично, мы получаем, что

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

Положим Теперь заметим, что

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

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

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

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

В самом деле, рассмотрим произвольное остовное дерево этого графа и подвесим его за любую не висячую вершину. Пусть — наиболее удалённая от корня висячая вершина этого дерева, а — предок этой вершины. Обозначим потомков этого предка через Заметим, что вершины являются висячими в рассматриваемом остовном дереве. Рассмотрим несколько случаев.

Случай 1. Среди вершин есть пара вершин, соединённых ребром в исходном графе. Тогда при удалении этих двух вершин остовное дерево(а значит, и сам исходный граф) сохраняет связность.

Случай 2. Среди вершин есть пара вершин, являющихся висячими в исходном графе. Значит, в исходном графе есть хотя бы две висячие вершины.

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

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

Заметим, что

Здесь мы оценили знаменатель по неравенству о средних:

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

Поскольку это равносильно неравенству

Но из неравенства между средним арифметическим и среднем квадратичным мы получаем, что

и, аналогично,

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

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

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

Из условия задачи следует, что точки лежат в одной плоскости, поэтому прямые и пересекают ребро в одной точке

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

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

Пример: В этом наборе три числа делятся на 5, четыре числа делятся на 4, а общая сумма равна

Первое решение. Рассмотрим граф дружб, в котором вершины — это люди, а ребро соединяет двух людей, если они дружат. Пусть в компании человека. Построим граф: одну вершину соединим с тремя другими Остальные вершин разобьём на пары и соединим вершины в каждой паре. Всего получаем 52 ребра. При удалении любой вершины исчезает нечётное число рёбер, значит, остаётся также нечётное число. Таким образом, компания из человек подходит. Покажем, что компаний больше чем из 102 людей быть не может, для этого выберем из них любые 103, достаточно показать, что не существует уже такой компании.

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

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Рассмотрим граф дружб, в котором вершины — это люди, а ребро соединяет двух людей, если они дружат. Пусть в компании человека. Построим граф: одну вершину соединим с тремя другими Остальные вершин разобьём на пары и соединим вершины в каждой паре. Всего получаем 52 ребра. При удалении любой вершины исчезает нечётное число рёбер, значит, остаётся также нечётное число. Таким образом, компания из человек подходит. Покажем, что компаний больше чем из 102 людей быть не может, для этого выберем из них любые 103, достаточно показать, что не существует уже такой компании.

Докажем, что компании из человек быть не может. Назовём вершину чётной, если её степень чётна, и нечётной иначе.

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

Случай 2. Общее количество рёбер чётно. Аналогично можно показать, что вершины одинаковой чётности соединены, а вершины разной чётности не соединены. Тогда число отсутствующих рёбер равно то есть общее число рёбер равно

что нечётно. Противоречие.

Назовём тройку натуральных чисел элементы которой принадлежат хорошей, если

Таким образом, нам надо найти наибольшее возможное количество хороших троек.

Выясним, когда тройка хорошая. Перепишем как квадратное уравнение относительно :

Решая его, получаем:

откуда

Иначе говоря, тройка является хорошей тогда и только тогда, когда одно из чисел и равно сумме двух других.

Пусть — все элементы множества Положим Оценим количество хороших троек в которых — наибольшее число, то есть

Заметим, что при любых есть не более одной такой тройки, в которой и (по этим значениям восстанавливается ). Поэтому оцениваемое количество не превосходит числа таких пар то есть

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

Эта оценка достигается, если положить то есть действительно, тогда при любых найдётся хорошая тройка

Записывая условие при и при получаем

и

то есть Отсюда и следует ответ.

Пример. Фишку 50 последовательно 99 раз меняем со следующей против часовой стрелки. Получаем требуемое расположение.

Есть несколько способов доказать оценку, ниже мы приведём два из них.

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

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

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

Тем самым, мы получаем, что фишки 1 и 100 совершают одинаковый сдвиг по и против часовой стрелки, поэтому они остаются на своих позициях. Противоречие.

_________________________________________________________________________________________________________________________________________________________________________________

Второй способ. Будем считать сдвиги фишек относительно их начальной позиции, причём сдвиг по часовой стрелке будет считаться с плюсом, против часовой — с минусом. Тогда при обмене двух фишек к сдвигу одной из них прибавляется +1, а другой — Значит, в результате проведённых операций общая сумма сдвигов будет равна 0.

Рассуждаем от противного: пусть при каждая фишка в итоге сдвинута на одну позицию по часовой стрелке, т.е. её сдвиг оказался равным (здесь — целое «число оборотов» по часовой стрелке, в частности при фишка сделала оборотов против часовой стрелки). Тогда суммарный сдвиг всех 100 фишек равен

Поскольку он должен равняться 0, имеем

Поскольку фишки с номерами и где не могли меняться местами, поэтому их сдвиги в любой момент заведомо отличаются меньше чем на 100, значит количества оборотов и равны при Отсюда имеем …, Тогда сумма

— чётна, а значит не равна Противоречие.

Из условия следует, что поскольку произведение цифр натурального числа не может быть отрицательным. Следовательно, числа и не содержат нулей в десятичной записи. Тогда эти числа отличаются лишь последней цифрой, причём у числа она больше на один. Таким образом, Если то, рассуждая аналогично, мы получим, что это противоречит доказанному выше. Следовательно, Тогда и в десятичной записи числа все цифры равны 1. Отсюда следует, что в числе последняя цифра — двойка, а остальные цифры — единицы, поэтому Значит, и число состоит лишь из единиц. Но тогда число не содержит нулей в десятичной записи. Однако, произведение его цифр равно нулю, противоречие.

Обозначим через центр окружности, описанной около трапеции Тогда

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

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

Значит, окружность, описанная около треугольника касается прямой поэтому

Отметим точку симметричную точке относительно точки Тогда

поэтому точки лежат на одной окружности.

Теперь заметим, что точки и симметричны относительно прямой Значит,

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