Выбрана 1 задача 
Убрать все задачи
а) Из точки A, лежащей вне окружности, выходят лучи AB и AC, пересекающие эту окружность. Докажите, что величина угла BAC равна полуразности угловых величин дуг окружности, заключенных внутри этого угла.
б) Вершина угла BAC расположена внутри окружности. Докажите, что величина угла BAC равна полусумме угловых величин дуг окружности, заключенных внутри угла BAC и внутри угла, симметричного ему относительно вершины A.
Решение
|
|
 |
Условие
В стране несколько городов, некоторые пары городов соединены двусторонними беспосадочными авиалиниями, принадлежащими k авиакомпаниям. Известно, что каждые две линии одной авиакомпании имеют общий конец. Докажите, что все города можно разбить на k + 2 группы так, что никакие два города из одной группы не соединены авиалинией.
Решение
Индукция по k.
База. Если k = 0, утверждение тривиально: авиалиний нет.
Шаг индукции. Рассмотрим граф, вершины которого соответствуют городам, а рёбра – авиалиниям.
Пусть E1, E2, ..., Ek – группы рёбер, соответствующие авиалиниям первой, второй, ..., k-й авиакомпаний. Нетрудно понять, что для любого i ∈ {1, ..., k} группа Ei – либо треугольник, либо ёж – несколько рёбер с одним концом. Если какая-то группа Ei – ёж с центром в вершине A, то удалим A и все выходящие из неё рёбра. В оставшемся графе рёбра принадлежат k – 1 авиакомпании, его вершины мы разобьём на k + 1 группу так, чтобы вершины из одной группы не были соединены ребром, а вершина A составит (k+2)-ю группу.
Остаётся рассмотреть случай, когда все группы E1, ..., Ek – треугольники. Тогда всего в графе 3k рёбер. Разобьём вершины графа на минимальное возможное количество групп так, что никакие две вершины одной группы не смежны.
Пусть это группы B1, ..., Bn, причём n ≥ k + 3. Отметим, что для каждых двух групп Bi и Bj существует ребро между вершиной из Bi и вершиной из Bj, иначе можно объединить эти две группы в одну. Таким образом, всего в графе хотя бы ½ n(n – 1) рёбер. Но ½ n(n – 1) ≥ (k + 3)(k + 2) > 3k. Противоречие.
