|
|
 |
Условие
В Академии Наук 999 академиков. Каждая научная тема интересует ровно троих академиков, и у каждых двух академиков есть ровно одна тема, интересная им обоим. Докажите, что можно выбрать 250 тем из их общей области научных интересов так, чтобы каждый академик интересовался не более чем одной из них.
Решение
Будем говорить, что две темы пересекаются по академику, если он интересуется обеими этими темами.
Выберем наибольшее возможное количество непересекающихся тем; пусть это темы T1, ..., Tk. Предположим, что k ≤ 249. Обозначим через S множество всех академиков, не интересующихся этими темами; тогда их ровно s = 999 – 3k ≥ 252.
Для каждых двух академиков a, b ∈ S существует единственная тема T(a, b), интересующая обоих. Третий академик, заинтересованный ею, не принадлежит S, иначе T(a, b) можно добавить к исходным k темам. Значит, его интересует какая-то тема Ti. Сопоставим эту тему (и этого академика) паре (a, b).
Итак, каждой из ½ s(s – 1) пар академиков из S сопоставлена одна из k тем T1, ..., Tk; значит, какая-то тема Ti сопоставлена не менее чем
s(s–1)/2k > s/2 парам. Обозначим эти пары (a1, b1), ..., (ad, bd); пусть Ti интересует академиков x, y, z. Поскольку d > s/2 > 6 один из x, y, z сопоставлен хотя бы трём парам (aj, bj); пусть, скажем, x сопоставлен парам (a1, b1), ..., (ap, bp) (p ≥ 3), а остальным парам сопоставлены y или z.
Пары (a1, b1), ..., (ap, bp) не пересекаются: если бы академик a находился в двух из них, то академиков a и x интересовали бы две общих темы. Значит, p ≤ s/2 < d, и паре (ap+1, bp+1) сопоставлен, скажем, академик y. Но тогда (ap+1, bp+1) не пересекается с одной из пар (a1, b1), (a2, b2),
(a3, b3), скажем, с (a1, b1). Значит, можно из нашего набора тем выбросить Ti и добавить непересекающиеся темы T(a1, b1) и
T(ap+1, bp+1), увеличив количество непересекающихся тем. Противоречие с исходным выбором.
