|
|
 |
Условие
300 бюрократов разбиты на три комиссии по 100 человек. Каждые два бюрократа либо знакомы друг с другом, либо незнакомы. Докажите, что найдутся два таких бюрократа из разных комиссий, что в третьей комиссии есть либо 17 человек, знакомых с обоими, либо 17 человек, незнакомых с обоими.
Решение
Для трёх бюрократов A, B, C из разных комиссий, будем говорить, что B и C похожи для A, если A либо знаком с обоими бюрократами B и C, либо незнаком с обоими. Для каждой пары бюрократов из разных комиссий найдём количество бюрократов в третьей комиссии, для которых они похожи. Оценим сумму s всех этих 3·100·100 чисел. В каждой тройке бюрократов A, B, C из разных комиссий есть либо две пары знакомых, либо две пары незнакомых между собой. Значит, два из них являются похожими для третьего, и вклад каждой тройки в сумму s не меньше 1. Следовательно, сумма s не меньше, чем число троек бюрократов, то есть s ≥ 100·100·100 = 106, и поэтому одно из слагаемых не меньше 106 : (3·104) = 100 : 3, то есть не меньше 34. Таким образом, какая-то пара бюрократов из разных комиссий является похожей не меньше чем для 34 бюрократов из третьей. Значит, эти два бюрократа либо знакомы хотя бы с 17 бюрократами из оставшейся комиссии, либо незнакомы хотя бы с 17 бюрократами из оставшейся комиссии.
