Задача 067 — Задачи на Графы

Дано натуральное число п. Назовём словом последовательность из $n$ нулей и единиц, а маской — последовательность из п нулей, единии, и звёздочек. Слово соответствует маске, если оно получено из неё заменой звёздочек на нули и единицы. Рассмотрим набор масок $\mathcal{M}$ , удовлетворяющий следующим двум условиям:

(1) каждое слово соответствует ровно одной маске, и

(2) для каждой из п позиций найдётся маска из $\mathcal{M}$ , в которой в этой позиции стоит не звездочка.

Найдите наименьшее возможное количество масок в таком наборе $\mathcal{M}$ .

Подсказка

Рассмотрим двудольный граф $G$ , в котором вершинами одной из долей будут номера позиций в слове длины $n$ , вершинами второй из долей будут маски, а рёбрами соединим каждую маску с теми позициями, на которых стоит не звездочка. Пусть доля $V_{1}$ это вершины $\{1,2 \ldots, n\}$ , соответствующие номерам позиций, а доля $V_{2}$ это вершины $\left\{u_{1}, u_{2} \ldots, u_{k}\right\}$ , соответствующие маскам.

Решение

Докажем, что в графе $G$ для доли $V_{1}$ выполнено условие леммы Холла. Предположим противное. Рассмотрим в $V_{1}$ минимальное по включению множество $A$ , для которого условие леммы Холла не выполнено. То есть у вершин из $A$ количество соседей меньше, чем $|A|$ , а для любого подмножества $B$ множества $A$ количество соседей у вершин из $B$ хотя бы $|B|$ . Отсюда следует, что у $A$ ровно $|A|-1$ соседних вершин. Без ограничения общности будем считать, что $A=\{1, \ldots, s+1\}$ , а $\left\{u_{1}, \ldots, u_{s}\right\}$ это соседние вершины множества $A$ . Тогда для множества $\{1, \ldots, s\}$ выполнена лемма Холла. Пусть без ограничения общности существует паросочетание $\left(1, u_{1}\right),\left(2, u_{2}\right), \ldots,\left(s, u_{s}\right)$ . Значит, в словах $u_{1}$ , $u_{2}, \ldots, u_{s}$ на $1,2, \ldots, s$ местах соответственно стоят не звёздочки (пусть без ограничения общности там стоят нули). Рассмотрим маски $u_{s+1}, \ldots, u_{k}$ . По построению в этих масках на местах с 1 по $s$ стоят звёздочки. Так как каждое слово можно получить из масок ровно одним способом, то из масок $u_{s+1}, \ldots, u_{k}$ получаются не все слова. Значит, существует множество слов $\underbrace{* * \ldots * *}_{s} \alpha$ (на первых $s$ позициях стоит что угодно, а затем идёт слово $\alpha$ длины $n-s$ ), которое нельзя получить из масок $u_{s+1}, \ldots, u_{k}$ . Тогда слово $\underbrace{1 \ldots 1}_{s} \alpha$ нельзя получить ни из какой маски. Противоречие.

Следовательно, для доли $V_{1}$ выполнено условие леммы Холла. Рассмотрим любое паросочетание, покрывающее долю $V_{1}$ . Пусть это паросочетание $\left(1, u_{1}\right),\left(2, u_{2}\right), \ldots,\left(n, u_{n}\right)$ , а в словах $u_{1}, u_{2}, \ldots, u_{n}$ на $1,2, \ldots, n$ местах соответственно стоят нули. Тогда чтобы получить слово $11 \ldots 11$ нам нужна ещё хотя бы одна маска. Откуда и получаем оценку на $n+1$ .