Закл (финал) 9 класс

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

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

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

Следовательно, Значит, для доказательства (*) достаточно показать, что

После раскрытия скобок и приведения подобных слагаемых остаётся неравенство

которое является суммой двух очевидных неравенств и

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

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

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

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

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

Отметим точку такую, что . Тогда в силу подобия треугольников и . Кроме того, проецируя на получаем . Следовательно, по двум катетам. А значит, — равнобедренная трапеция и лежит на окружности, описанной около

и Следовательно, — касательная к окружности, описанной около треугольника

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

Оценка. Заметим, что значит, Но и  – целые числа, поэтому Следовательно,

Стало быть, то есть

Пример. Оценка достигается при

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

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

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

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

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

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

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

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

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

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

Получим

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

или

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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