Доказать, что в 8K конъюнкциях, по три буквы в каждой, всегда найдётся К

Nonnik

штук пересечение которых непусто.
Для восьми правильно, для 16 тоже правильно, для 24 фиг его знает как проверить, но тоже вроде правильно.
Как доказать?
Заранее спасибо.

888julia888

не понял. пеши подробней.

Nonnik

Есть формула в виде 3-ДНф, например
F= X1x2x3 v X2X3X4 v X2x3x5 v .... .v X1X4X5
(большие буквы означают отрицание)
Число конъюкций в формуле F - M штук. Надо показать, что если М = 8*K, то всегда в формуле F найдётся К конъюнкций, пересечение которых непусто (то есть сущестует вектор, который все эти К конъюнкций обращает в 1)

Xephon

Пусть в записи используются только переменные x1,...,x_{g+3} и их отрицания.
Заменим каждую 3-коньюнкцию A из начальной формулы на множество A* из 2^g коньюнкций, использующих все переменные (дополнив по-разному её).
Ясно, что на любом векторе значений b_1,...,b_{g+3} максимум одна коньюнкция из A* будет истинна.
Рассмотрим тогда получившееся множество из 8*k*2^g=k*2^{g+3} полных коньюнкций на g+3 переменных. По принципу Дирихле в нём, есть подмножество из k одинаковых. Очевидно, существует вектор, который их одновременно удовлетворяет - значит они все взяты из разных A*, и соответствующие 3-коньюнкции --- искомые.

Nonnik

Спасибо ОГРОМНОЕ!
Два дня мозг пропарил)
Оставить комментарий
Имя или ник:
Комментарий: