В компании из 300 человек каждый знаком ровно с тремя другими. При каком наименьшем 
про такую компанию можно наверняка утверждать, что среди любых человек найдутся двое знакомых?
Подсказка
Попробуйте для начала подумать над компанией из 150 человек.
Решение
Ответ: 151.
Решение: Допустим, удалось выбрать 151 человека, не знакомых друг с другом. У них вместе 453 знакомства с оставшимися 149 людьми, но у тех вместе всего 447 знакомств — противоречие. Таким образом, среди любых 151 человека найдутся двое знакомых. Покажем, что 150 человек, не знакомых друг с другом, могут найтись. Разобьём компанию на 50 шестёрок, каждую шестёрку — на две тройки, и пусть в каждой шестёрке каждый человек из одной тройки знаком с каждым человеком из другой; в набор из 150 человек возьмём по одной тройке из каждой шестёрки.