|
|
 |
Условие
Доказать, что в любой группе из 12 человек можно выбрать двоих, а среди оставшихся 10 человек еще пятерых так, чтобы каждый из этих пятерых удовлетворял следующему условию: либо он дружит с обоими выбранными вначале, либо не дружит ни с одним из них.
Решение
Предположим, что это не так. Выбрав любых двух человек A и B, среди оставшихся десятерых выберем таких людей C1, C2, ..., Ck, каждый из которых знает ровно одного в этой паре. В силу предположения k ≥ 6. Подсчитаем число N троек {A, В, Ci} двумя способами. Всего имеется 12·11 : 2 = 66 пар {A, В}, и каждой паре отвечает не менее шести человек Сi, поэтому N ≥ 6·66 = 396. С другой стороны, Ci можно фиксировать и искать для него такие пары {A, В}, в которых он знает ровно одного человека. Если у Сi есть n знакомых, то число искомых пар {A, В} равно n(11 − n) ≤ 30. Выбрать же Сi можно 12 способами, откуда N ≤ 5·6·12 = 360. Противоречие.
