Нижняя оценка числа способов

[grizzly]

sup
Очень интересно получилось. Не то чтоб очень сложное решение, но хитросплетение разных идей (прямой пересчёт, индукция, обнуление множества $B$) делает его как минимум нестандартным. Спасибо!

[sup]

Да там можно и без обнуления. Просто у меня было сразу несколько возможных вариантов сведения множества $U$ к некому "каноническому" виду. В числе других были побитовая сортировка, обмены и XOR. А в результате получилась какая-то избыточная смесь. Ну, может для решения других задач хоть что-нибудь пригодится.

Без обнуления все аналогично. Напомню, что

$$ U \# (I_n \setminus U) = |A| + |B| + 2A \# B + A\#Y + B\#Y + A\#X + B\#X + 2X\#Y$$

Отсюда

$$ U \# (I_n \setminus U) = |A| + |B| + 2A \# B + X\# (A \bigcup B \bigcup Y) + Y\# (A \bigcup B \bigcup X)$$

А значит
$$ U \# (I_n \setminus U) \geqslant |A| + |B| + 2|X| = |U|$.

[grizzly]

Я упустил самое, может быть, главное -- удачное разбиение по множествам. И оказалось, что можно вот так просто взять и всё пересчитать. Я был очень далёк от такой попытки.

sup в сообщении #1033870 писал(а):

Ну, может для решения других задач хоть что-нибудь пригодится.

Вот, кстати, за это отдельное спасибо. Я как раз тоже подумал насчёт что-то куда-то попробовать

[Evgenjy]

sup в сообщении #1033870 писал(а):

А значит
$$ U \# (I_n \setminus U) \geqslant |A| + |B| + 2|X| = |U|$.

Точнее
$ U \# (I_n \setminus U) \geqslant |A| + |B| + |X| + |Y|= |U|$

[grizzly]

Evgenjy в сообщении #1033890 писал(а):

Точнее...

Нет.

[Evgenjy]

Вы правы, я ошибся.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Олимпиадные задачи (М)»
Причина переноса: в более подходящий раздел