Выбрано 8 задач 
Убрать все задачи
Окружность, вписанная в угол с вершиной O касается его сторон в точках A и B , K – произвольная точка на меньшей из двух дуг AB этой окружности. На прямой OB взята точка L такая, что прямые OA и KL параллельны. Пусть M – точка пересечения окружности , описанной около треугольника KLB , с прямой AK , отличная от K . Докажите, что прямая OM касается окружности .
Дан выпуклый четырёхугольник ABCD . Пусть P и Q – точки пересечения лучей BA и CD , BC и AD соответственно, а H – проекция D на PQ . Докажите, что четырёхугольник ABCD является описанным тогда и только тогда, когда вписанные окружности треугольников ADP и CDQ видны из точки H под равными углами.
В треугольнике ABC взята такая точка O, что ∠COA = ∠B + 60°, ∠COB = ∠A + 60°, AOB = ∠C + 60°. Докажите, что если из отрезков AO, BO и CO можно составить треугольник, то из высот треугольника ABC тоже можно составить треугольник и эти треугольники подобны.
Через точку пересечения высот остроугольного треугольника ABC проходят три окружности, каждая из которых касается одной из сторон треугольника в основании высоты. Докажите, что вторые точки пересечения окружностей являются вершинами треугольника, подобного исходному.
Набор пятизначных чисел {N1 , Nk} таков, что любое пятизначное число, все цифры которого идут в неубывающем порядке, совпадает хотя бы в одном разряде хотя бы с одним их чисел N1 , Nk . Найдите наименьшее возможное значение k .
У выпуклого многогранника 2n граней ( n 3 ), и все грани
являются треугольниками. Какое наибольшее число вершин, в которых
сходится ровно 3 ребра, может быть у такого многогранника?
На плоскости отмечено несколько точек. Для любых трех из них существует декартова система координат (т.е. перпендикулярные оси и общий масштаб), в которой эти точки имеют целые координаты. Докажите, что существует декартова система координат, в которой все отмеченные точки имеют целые координаты.
В стране есть N городов. Некоторые пары из них соединены беспосадочными двусторонними авиалиниями. Оказалось, что для любого k (2 ≤ k ≤ N) при любом выборе k городов количество авиалиний между этими городами не будет превосходить 2k – 2. Докажите, что все авиалинии можно распределить между двумя авиакомпаниями так, что не будет замкнутого авиамаршрута, в котором все авиалинии принадлежат одной компании.
|
|
 |
Условие
В стране есть N городов. Некоторые пары из них соединены беспосадочными двусторонними авиалиниями. Оказалось, что для любого k (2 ≤ k ≤ N) при любом выборе k городов количество авиалиний между этими городами не будет превосходить 2k – 2. Докажите, что все авиалинии можно распределить между двумя авиакомпаниями так, что не будет замкнутого авиамаршрута, в котором все авиалинии принадлежат одной компании.
Решение
Рассмотрим граф, вершины которого – это города, а рёбра – авиалинии. Обобщим задачу – разрешим графу иметь кратные рёбра. При этом для каждого набора из k вершин количество рёбер между ними не превосходит 2k – 2. Требуется доказать, что можно покрасить рёбра графа в два цвета так, чтобы не было одноцветных циклов.
Назовём непустое подмножество A вершин графа критическим,
если количество рёбер графа между вершинами множества A – ровно 2|A| – 2.
Лемма. Если A и B – критические подмножества, причём A ∩ B ≠ ∅, то A ∪ B – тоже критическое.
Доказательство. Пусть C = A ∩ B, D = A ∪ B и D – не критическое. Пусть |A| = a, |B| = b, |C| = c, |D| = d = a + b – c. Так как количество рёбер в A равно 2a – 2, а количество рёбер в D меньше чем 2d – 2, то число рёбер, соединяющих вершины из D, у которых не оба конца лежат в A, меньше
(2d – 2) – (2a – 2) = 2(d – a) = 2(b – c). В частности, в число этих рёбер входят все рёбра, соединяющие вершины B, не обе из которых лежат в C. Поэтому их число также меньше 2(b – c), а число остальных рёбер среди вершин B – больше (2b – 2) – 2(b – c) = 2c – 2. Но это в точности рёбра, соединяющие вершины множества C; значит, C не удовлетворяет условию задачи. Противоречие.
Заметим, что в условиях леммы множество C также будет критическим.
Перейдём к решению задачи. Предположим противное и рассмотрим граф с минимальным числом вершин n, для которого утверждение задачи не выполняется. Рассмотрим все его вершины. Число рёбер между ними не больше 2n – 2. Если степень каждой вершины не меньше 4, то общее количество рёбер не меньше 4n : 2 = 2n > 2n – 2, что невозможно. Значит, найдётся вершина a степени не больше 3. Если её степень меньше 3, то выкинем её; рёбра оставшегося графа можно покрасить требуемым образом, так как он, очевидно, удовлетворяет условию. Покрасив после этого ребра из вершины a в разные цвета, мы, очевидно, не образуем одноцветных циклов, и требуемая раскраска получена.
Итак, степень a равна 3, и она соединена с вершинами b, c, d. Все три вершины b, c, d не могут совпадать, так как иначе между двумя вершинами a и b было бы больше 2·2 – 2 рёбер, что невозможно. Тогда среди b, c и d есть вершина, отличная от обеих остальных – пусть это вершина c.
Выбросим из графа вершину a. Если в оставшемся графе пара вершин b и c не принадлежит одновременно никакому критическому подмножеству, то после добавления фиктивного ребра (b, c) мы получим граф, удовлетворяющий условию задачи, число вершин в котором меньше, чем в нашем (см. рис.). Покрасим его рёбра требуемым образом, потом удалим добавленное ребро, вернём вершину a и покрасим рёбра (a, b) и (a, c) в цвет фиктивного ребра, а ребро (a, d) в другой. Очевидно, одноцветных циклов не появится.
