В компании 100 человек, причем каждый из них знаком с 50 членами компании. Известно, что нет троих, попарно знакомых друг с другом (то есть если Х знаком с Y, а Y знаком с Z, то Z не знаком с X). Докажите, что не найдется пятерых из них А, В, С, D и E, знакомых по кругу (А с В, В с С, С с D, D с Е, Е с А.

Возьмем двух знакомых A и B, у каждого из них хотя бы по 50 знакомых. Складываем количества их знакомых, получаем хотя бы 50 + 50 = 100. Общих знакомых у них нет, по условию задачи, значит, никого не посчитали дважды. (A посчитали как знакомого B, а B как знакомого A). Поскольку людей 100, то каждого посчитали один раз. Следовательно, каждый из остальных знаком с одним из них либо с A, либо с B.

Предположим, что есть 5 знакомых по кругу (А с В, В с С, С с D, D с Е, Е с А), тогда D должен быть знаком либо с A, либо с B, так как мы доказали, что каждый из остальных знаком либо с А, либо с В. В любом случае получаются попарно знакомые A - D - E или B - C - D. Получили противоречие. Значит, не найдется пятерых из 100 А, В, С, D и E, знакомых по кругу.