Простая задача по комбинаторике

Условия задачи:

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

Ответ

Решение

Ответ: При k = 15. А при k &lt, 15 два человека, нравящиеся друг другу, могут и не найтись. В самом деле, расположим 30 человек по кругу. Может оказаться, что каждому человеку нравятся k следующих за ним по часовой стрелке людей.

Ответ: При k = 15.