Maths Olympiad Prep

Library / /36 of 57

Combinatorics Difficulty 7.0 National olympiad Prove it Russia

In Academy of Sciences, there are 999999 academicians. For each scientific topic there are exactly 33 academicians interested in this topic. For each pair of academicians, there exists exactly one topic in which both these academicians are interested. Prove that there exists a set of 250250 topics such that each academician is interested in not more than one topic from this set. (A. Magazinov)

В Академии Наук 999999 академиков. Каждая научная тема интересует ровно троих академиков, и у каждого двух академиков есть ровно одна тема, интересная им обоим. Докажите, что можно выбрать 250250 тем из их общей области научных интересов так, чтобы каждый академик интересовался не более, чем одной из них. (А. Магазинов)

Solution

Будем говорить, что две темы пересекаются по академику, если он интересуется обеими этими темами.

Выберем наибольшее возможное количество непересекающихся тем; пусть это темы T1,,TkT_1, \dots, T_k. Предположим, что k249k \le 249. Обозначим через SS множество всех академиков, не интересующихся этими темами; тогда их ровно s=9993k252s = 999 - 3k \ge 252.

Для каждого двух академиков a,bSa, b \in S существует единственная тема T(a,b)T(a, b), интересующая обоих. При этом третий академик, заинтересованный ею, не должен принадлежать SS, иначе T(a,b)T(a, b) можно добавить к исходным kk темам. Значит, его интересует какая-то тема TiT_i. Сопоставим эту тему (и этого академика) паре (a,b)(a, b).

Итак, каждой из s(s1)2\frac{s(s-1)}{2} пар академиков из SS сопоставлена одна из kk тем T1,,TkT_1, \dots, T_k; значит, какая-то тема TiT_i сопоставлена не менее, чем s(s1)2k>s2\frac{s(s-1)}{2k} > \frac{s}{2} парам. Обозначим эти пары (a1,b1),,(ad,bd)(a_1, b_1), \dots, (a_d, b_d); пусть TiT_i интересует академиков x,y,zx, y, z. Поскольку d>s2>6d > \frac{s}{2} > 6, один из x,y,zx, y, z сопоставлен хотя бы трём парам (aj,bj)(a_j, b_j); пусть, скажем, xx сопоставлен парам (a1,b1),,(ap,bp)(a_1, b_1), \dots, (a_p, b_p) (p3p \ge 3), а остальным парам сопоставлены yy или zz.

Заметим, что все пары (a1,b1),,(ap,bp)(a_1, b_1), \dots, (a_p, b_p) не пересекаются: если бы академик aa находился в двух из них, то академиков aa и xx интересовали бы две общих темы. Значит, ps2<dp \le \frac{s}{2} < d, и паре (ap+1,bp+1)(a_{p+1}, b_{p+1}) сопоставлен, скажем, академик yy. Но тогда (ap+1,bp+1)(a_{p+1}, b_{p+1}) не пересекается с одной из пар (a1,b1),(a2,b2),(a3,b3)(a_1, b_1), (a_2, b_2), (a_3, b_3), скажем, с (a1,b1)(a_1, b_1). Значит, можно из нашего набора тем выбросить TiT_i и добавить непересекающиеся темы T(a1,b1)T(a_1, b_1) и T(ap+1,bp+1)T(a_{p+1}, b_{p+1}), увеличив количество непересекающихся тем. Противоречие с исходным выбором.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.