ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 34851
Темы:    [ Принцип Дирихле (прочее) ]
[ Сочетания и размещения ]
[ Ориентированные графы ]
Сложность: 3
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

В дискуссии приняли участие 15 депутатов. Каждый из них в своем выступлении раскритиковал ровно k из оставшихся 14 депутатов.
При каком наименьшем k можно утверждать, что найдутся два депутата, которые раскритиковали друг друга?


Подсказка

Рассмотрите ориентированный граф, вершины которого соответствуют депутатам, а ребро, ведущее из A в B, означает, что депутат A раскритиковал депутата B.


Решение

  Если каждый депутат раскритиковал 8 других, то число рёбер указанного в подсказке графа равно  15·8 = 120,  что больше, чем число пар   его вершин. Это доказывает, что какие-то две вершины соединяются не менее чем двумя рёбрами, то есть найдутся два депутата, которые раскритиковали друг друга.
  С другой стороны, пусть 15 депутатов сидят за круглым столом и каждый раскритиковал семь следующих за ним по часовой стрелке. Легко видеть, что при этом никакие два депутата не критиковали друг друга.


Ответ

При  k = 8.

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

web-сайт
задача

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .