44*. В компании из 25 человек каждый знаком как минимум с 13 другими. Докажите, что найдутся трое, которые попарно знакомы друг с другом.

Выберем любого человека A. Он знаком как минимум с 13 людьми. Предположим, что среди этих 13 знакомых нет двух знакомых между собой.

Каждый из 13 знакомых A уже знаком с A и не знаком с остальными 12 знакомыми A. Поэтому, чтобы иметь не менее 13 знакомых, каждый из них должен быть знаком со всеми 12 людьми, не входящими в эту группу.

Рассмотрим этих 12 человек. Каждый из них знаком со всеми 13 знакомыми A. Кроме того, по условию каждый человек знаком как минимум с 13 людьми, значит, каждый из этих 12 человек должен быть знаком ещё хотя бы с одним человеком из своей группы.

Пусть B и C — два таких знакомых человека. Тогда любой знакомый A из группы из 13 человек знаком и с B, и с C. Если B и C знакомы, то они вместе с этим человеком образуют тройку попарно знакомых. Противоречие с предположением.

Следовательно, в компании обязательно найдутся трое, которые попарно знакомы.