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

   Решение

Около окружности, радиус которой равен 4, описан прямоугольный треугольник, гипотенуза которого равна 26. Найдите периметр треугольника.

   Решение

Две окружности радиусов 3 и 4, расстояние между центрами которых равно 5, пересекаются в точках A и B. Через точку B проведена прямая, пересекающая окружности в точках C и D, причём CD = 8 и точка B лежит между точками C и D. Найдите площадь треугольника ACD.

   Решение

Внутри тетраэдра расположен треугольник, проекции которого на 4 грани тетраэдра имеют площади P₁, P₂, P₃, P₄. Докажите, что а) в правильном тетраэдре P₁ ≤ P₂ + P₃ + P₄; б) если S₁, S₂, S₃, S₄ — площади соответствующих граней тетраэдра, то P₁S₁ ≤ P₂S₂ + P₃S₃ + P₄S₄.

   Решение

Найдите диагонали четырёхугольника, образованного биссектрисами внутренних углов прямоугольника со сторонами 1 и 3.

   Решение

В кубе ABCDA1B1C1D1 , где AA1 , BB1 , CC1 и DD1 – параллельные рёбра, плоскость P проходит через противоположные вершины A1 , C и середину ребра D1C1 . Найдите расстояние от вершины D1 до плоскости P , если ребро куба равно 6.

   Решение

Какую наименьшую длину должен иметь кусок проволоки, чтобы из него можно было согнуть каркас куба с ребром 10 см?
(Проволока может проходить по одному ребру дважды, загибаться на 90° и 180°, но ломать её нельзя.)

Темы:    [ Теория графов (прочее) ] [ Степень вершины ] [ Принцип крайнего (прочее) ] [ Неравенство Коши ] [ Разбиения на пары и группы; биекции ]

Сложность: 4 Классы: 6,7,8

Прислать комментарий

Условие

а) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет треугольников?
б) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет полного подграфа из четырёх вершин?

Подсказка

Выберите вершину наибольшей степени.

Решение

  а) Оценка. Выберем вершину A наибольшей степени n и рассмотрим подграф G, образованный вершинами, куда ведут рёбра из A. Ясно, что в этом подграфе рёбер нет. Каждая вершина, не входящая в G имеет степень не больше n, а выходящие из них рёбра – это все рёбра исходного графа. Таким образом, общее число рёбер исходного графа не превосходит  n(30 – n) ≤ 15².
  Пример. Разобьём 30 вершин на две группы по 15 и проведём все рёбра, соединяющие вершины из разных групп. Получился граф без треугольников с 225 рёбрами.

  б) Оценка. Выберем вершину A наибольшей степени n и рассмотрим подграф G, образованный вершинами, куда ведут рёбра из A. Ясно, что в этом подграфе нет треугольников, поэтому, как фактически доказано в а), число его рёбер не превосходит (ⁿ/₂)². Таким образом, общее число рёбер исходного графа не превосходит  (n/₂)² + n(30 – n) = ³/₄ n(40 – n) ≤ ³/₄·20² = 300.
  Пример. Разобьём 30 вершин на три группы по 10 и проведём все рёбра, соединяющие вершины из разных групп. Получился граф без полных 4-подграфов с 300 рёбрами.

Ответ

а) 225;  б) 300 рёбер.

Замечания

Эти задачи – частные случаи теоремы Турана (см. статью в Википедии).

Источники и прецеденты использования