Закл до 2015

Четырехугольник вписан в окружность только тогда, когда произведение длин отрезков секущиx и равны.

Точки и симметричны точкам и относительно середин отрезков и соответственно, следовательно, и то есть достаточно проверить равенство

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

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

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

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

Перемножив равенство

и неравенство

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

Возведем теперь в квадрат равенство

Получим

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

или

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

Но, если вычесть из квадрата равенства равенство получится равенство

что противоречит Значит, найдутся два числа, отличающиеся больше, чем на

Обозначим Тогда Поскольку четырёхугольник вписан, и Пусть — высота треугольника а — точка пересечения прямых и Без ограничения общности можно считать, точка лежит на луче

Угол — внешний угол треугольника поэтому Значит, четырёхугольник вписан, и Пусть — точка пересечения прямых и Вновь по свойству внешних углов

Итак, то есть — ортоцентр треугольника

Докажем индукцией по

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

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

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

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

Достроим треугольник до параллелограмма Отрезок делит сторону пополам, поэтому лежит на прямой причём Кроме того, и поэтому и — высоты треугольника Значит, — ортоцентр этого треугольника и

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

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

Таким образом, если общее количество диагоналей в многоугольнике нечётно, то выиграет первый, а если чётно — второй. В угольнике число диагоналей равно то есть нечётно при чётном и чётно при нечётном

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

Из условия не имеет корней, следовательно:

Аналогично, из не имеет корней:

Не умаляя общности тогда и следовательно не имеет корней.

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

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

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

База. Для полного графа с тремя вершинами утверждение очевидно.

Шаг индукции. Рассмотрим полный граф с вершиной. Удалим из рассмотрения одну вершину с выходящими из неё ребрами. Для оставшегося графа с вершинами по предположению индукции существует цикл, проходящий через все вершины, состоящий не более чем из двух одноцветных частей. Возможны два случая.

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

2) Не все рёбра цикла окрашены в один цвет. Пусть в цикле есть две одноцветные части: (красная) и (синяя). Посмотрим на цвет ребра Если это ребро красное, то цикл — искомый, если же оно синее, то искомым будет цикл

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

Если среди этих рёбер присутствуют рёбра ровно трёх цветов, то искомый набор найден.

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

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

Это означает, что требуемый набор вершин можно выбрать всегда.

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

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

Пусть у первых двух уравнений общий корень . Тогда и (по условию ). Тогда второй корень у уравнения по теореме Виета это . Отсюда . Посмотрим на оставшиеся уравнения.

Пусть у последних двух уравнений общий корень . Тогда и . Значит корень и . Отсюда . Если , то у уравнения нет корней ?! Значит . Подставим 1 во все уравнения, где корень и получим и . Значит .

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

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

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

Получаем противоречие. Значит, нашлись комитета, имеющих более общих членов.

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

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

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

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

Проведем через точку прямую, параллельную Отметим на ней точку так, чтобы

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

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

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

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