В группе из 80 человек некоторые знакомы друг с другом (знакомства взаимны). Известно, что в группе есть человек, который знает ровно 1 из оставшихся, человек, который знает ровно 2 из оставшихся, . . . , человек, который знает ровно 54 из оставшихся. Докажите, что в группе есть три человека, каждые два из которых знакомы.

Решение

Пусть у человека \(A\) 54 знакомых. Среди них не больше \(80-54=26\) человек, про которых мы не можем сказать, сколько у них знакомых. Остается 28 человек, про количество знакомы которых есть информация в условии. Среди этих знакомых человека \(A\) найдется человек \(B,\) у которого есть хотя бы 28 знакомых. У \(A,\) кроме \(B,\) есть 53 знакомых, а у \(B,\) кроме \(A\) \(-\) еще 27. Поскольку \(53+27=80>78,\) то у \(A\) и \(B\) есть общий знакомый \(C.\) Тогда \(A,B,C\) \(-\) искомая тройка знакомых.