Найдите наименьшее значение функции y = 8x-2 sin x+4 на отрезке [0;] .

   Решение

Пусть m, n и k – натуральные числа, причём  m > n.  Какое из двух чисел больше:

    или  

(В каждом выражении k знаков квадратного корня, m и n чередуются.)

   Решение

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

Сложность: 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 рёбер.

Замечания

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

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