|
|
 |
Условие
В дискуссии приняли участие 15 депутатов. Каждый из них в своем выступлении раскритиковал ровно k из оставшихся 14 депутатов. При каком наименьшем k можно утверждать, что найдутся два депутата, которые раскритиковали друг друга?
Подсказка
Рассмотрите ориентированный граф, вершины которого соответствуют депутатам, а ребро, ведущее из A в B, означает, что депутат A раскритиковал депутата B.
Решение
Если каждый депутат раскритиковал 8 других, то число рёбер указанного в подсказке графа равно 15·8 = 120, что больше, чем число пар его вершин. Это доказывает, что какие-то две вершины соединяются не менее чем двумя рёбрами, то есть найдутся два депутата, которые раскритиковали друг друга.
С другой стороны, пусть 15 депутатов сидят за круглым столом и каждый раскритиковал семь следующих за ним по часовой стрелке. Легко видеть, что при этом никакие два депутата не критиковали друг друга.
Ответ
При k = 8.
Источники и прецеденты использования
| web-сайт | |
| задача |
