Задача 058

Ответ. 2695. Решение. Покажем, как могло оказаться 2695 человек. Разобьём их на 4 группы размером и 673 . Сделаем людей внутри одной группы незнакомыми, а в разных — знакомыми.

Ответ. 2695. Решение. Покажем, как могло оказаться 2695 человек. Разобьём их на 4 группы размером и 673 . Сделаем людей внутри одной группы незнакомыми, а в разных — знакомыми. Тогда у каждого человека знакомых минимум , а пяти попарно знакомых точно нет.
Докажем, что менее 2695 человек быть не могло. Предположим, что у нас людей. Тогда у каждого не более незнакомых. Будем набирать группу из попарно знакомых. Когда мы добавляем к ней любого человека, он запретит с учётом себя не более . Поскольку , то после того как наберём не более четверых, не запрещённые останутся, поэтому можно будет добавить человека в нашу группу. Получается, найдётся группа из 5 попарно знакомых.