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