|
Даю мастер-класс по комбинаторике.
Решение задачи 3.
Пусть k - наибольшее число, для которого есть две НЕПЕРЕСЕКАЮЩИЕСЯ компании размера k. Следовательно, нет компании размера 2k+2 (иначе её можно было бы разбить на две компании размера k+1), а значит - нет и большей компании. А тогда нет и компании размера 2k+1, иначе размер максимальной компании был бы нечётным.
Пусть K_1 и K_2 - непересекающиеся компании размера k.
Разместим K_1 в одну комнату, а остальных - в другую. Если во второй комнате (а там есть K_2) нет компании размера k+1, то всё классно.
Если во второй комнате есть компания размера k+1 (назовём её L), то оставим L во второй комнате, а остальных перебросим в первую. Пока что в первой комнате есть компания из k человек (K_1) и, по выбору k, нет большей. Рассмотрим некоторого человека u в компании L. Если при его перебрасывании в первую комнату в ней не появляется компания размера k+1, то всё отлично.
Пусть такая компания появляется. Сначала рассмотрим случай, когда такая компания одна. Назовём её M_1. Тогда M_1\{u} - это компания размера k. В M_1\{u} найдётся чувак v, который не дружит со всеми участниками из L\{u}. [В противном случае L+(M_1\{u}) - это компания размера 2k+1 ("+" означает объединение).] Тогда пусть во второй комнате будут L\{u} и v, а в первой - все остальные. Всё супер.
И наконец, пусть при переводе u из второй комнаты (где была только компания L) в первую комнату, там появляется НЕСКОЛЬКО компаний размера k+1 - назовём их M_1, M_2, ..., M_n. Причём пусть M_1 и M_2 - это такие компании, пересечение которых - НАИБОЛЬШЕЕ среди всех возможных пересечений M_i и M_j (i<j). Тогда никакая другая M_i (i>2) не содержится в M_1+M_2 (+ означает объединение). [Иначе M_i должна была бы покрывать (M_1\M_2)+(M_2\M_1), а тогда (M_1\M_2)+(M_2\M_1) - компания, а значит и M1+M2 - компания, причём размера больше k+1. Тогда, выдёргивая u обратно к L, получаем, что есть две непересекающиеся компании размера k+1: L и некоторое подмножество (M_1+M_2)\{u} - возможно, сама (M_1+M_2)\{u}.]
Значит, в каждой M_i (i>2) можно выбрать человека v_i, который не принадлежит M_1+M_2 (все v_i не обязаны быть различными). Перебрасывая v_3, ..., v_n во вторую комнату (к L\{u}), мы НЕ ПОЛУЧИМ компании размера k+1 во второй комнате (так как таковые есть в первой - M_1 и M_2). Рассмотрим некоторых людей v_1 из M_1\M_2 и v_2 из M_2\M_1, которые НЕ ДРУЖАТ. Они найдутся, поскольку M_1+M_2 - не компания. Заметим, что (L\{u})+{v_1, v_3, ..., v_n} не содержит компании размера k+1, поскольку существует не пересекающаяся с этим множеством (k+1)-компания M_2. Аналогично и (L\{u})+{v_2, v_3, ..., v_n} не содержит компании размера k+1. Но тогда в (L\{u})+{v_1, v_2, v_3, ..., v_n} может быть только (k+1)-компания, содержащая и v_1, и v_2. Но такой компании нет, поскольку v_1 и v_2 не дружат. :)
Итак, в (L\{u})+{v_1, v_2, v_3, ..., v_n} (вторая комната) нет компании размера k+1, но есть k-компания L\{u}. В первой комнате мы уничтожили все компании размера k+1 (которые суть M_1, M_2, ..., M_n). Компания из k человек осталась - например, M_1\{v_1}. Ура-а-ааа!!!!
|
