На турнир приехали 100 человек. Известно, что среди любых 50 из них есть человек, знакомый с остальными 49. Докажите, что можно найти 52 человека, любые два из которых знакомы между собой.
Подсказка
Выберем из этих 100 человек наибольшее возможное количество пар незнакомых.
Решение
Выберем из этих 100 человек наибольшее возможное количество пар незнакомых. Если таких пар наберется 25 , среди входящих в них 50 человек не найдется никого, кто был бы знаком с 49 остальными — противоречие. Значит, таких пар не больше 24 , и в них входит не больше 48 человек. Понятно, что среди 52 (или большего числа) остальных людей каждый знает каждого, что и требовалось доказать.