Соответствия, сравнения, количества

(a) Давайте попробуем придумать контрпример. Пусть у нас есть элементы Все двухэлементные множества, которые из них могут получится выглядят так: и Как можно по другому сформулировать условие задачи? Можно сказать, что у нас нет трёх двухэлементных множеств, которые не пересекаются между собой. Тогда для наших множеств условие выполняется, так как тут всего различных элемента, а в противном случае их должно быть минимум Пусть мы смогли прибить это множество. Не умаляя общности, пусть множества прибили элементами и Но тогда существует множество которое оказалось не прибито. Значит, не всегда можно прибить такое семейство двумя гвоздями.

(b) Поймём по аналогии с прошлым пунктом, что гвоздей тоже не хватит. Пусть у нас есть пять различныъ элементов и рассмотрим все их двухэлементные множества. Тогда условие задачи аналогично выполняется(всего элементов, что меньше Теперь если мы возьмём элемента, которыми прибили семейство, то останется просто элемента, образующие множество. Но оно никак не прибито. Получаем, что гвоздей не хватит. Докажем, что точно хватит гвоздей. Если у нас есть среди семейства два непересекающихся множества, то прибьём гвоздями их элемента. Тогда мы знаем, что не существует третьего множества, которое с ними не пересекается(иначе нарушено условие). Значит, остальные множества будут пересекаться с этими двумя и, следовательно, будут прибиты. Если же у нас не существует двух непересекающихся множеств, то это значит, что если мы возьмём какое-то одно множество, то все остальные будут с ним пересекаться. В таком случае хватит и двух гвоздей.

(c) Решим задачу в общем виде. Теперь условие задачи можно понимать так, что у нас нет двухэлементных множеств, которые не пересекаются между собой. Тогда рассмотрим различных элементов. Возьмём семейство, состоящее из этих всевозможных двухэлементных множеств. Теперь мы понимаем, что нам не хватит (или меньше) гвоздей, так как в таком случае останутся хотя бы два элемента, образующие множество, но оно не прибито. Получаем, что точно нужно гвоздей. Почему столько хватит? Давайте рассмотрим максимальное количество непересекающихся множеств. Пусть их где Тогда оставшиеся точно пересекаются с каким-то из этих. В таком случае можем выбрать элементов в этих множествах, прибить их, и тогда все множества окажутся прибиты. Причём точно не больше