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

   Решение

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

   Решение

В прямоугольном треугольнике ABC  (∠B = 90°)  проведена высота BH. Окружность, вписанная в треугольник ABH, касается сторон AB, AH в точках H₁, B₁ соответственно; окружность, вписанная в треугольник CBH, касается сторон CB, CH в точках H₂, B₂ соответственно. Пусть O – центр описанной окружности треугольника H₁BH₂. Докажите, что  OB₁ = OB₂.

   Решение

В ориентированном графе 101 вершина. У каждой вершины число входящих и число выходящих рёбер равно 40.

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

   Решение

Темы:    [ Ориентированные графы ] [ Принцип Дирихле (прочее) ]

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

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

Условие

В ориентированном графе 101 вершина. У каждой вершины число входящих и число выходящих рёбер равно 40.

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

Решение

См. задачу 30830 б).

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