Верещагин, Шень. Эквивалентность и порядок

[caxap]

87. Пусть $U$ -- конечное множество из $n$ элементов. Рассмотрим множество $\mathcal P(U)$ всех подмножеств множества $U$, упорядоченное по включению. Какова максимально возможная мощность множества $S\subset \mathcal P(U)$,
а) если индуцированный на $S$ порядок линейный?
б) если никакие два элемента $S$ не сравнимы?

-------
a) Возьмём один любой элемент $s_1\in \mathcal P(U)$ мощности 1 из $\mathcal P(U)$. Затем возьмём из $\mathcal P(U)$ один элемент $s_2$ мощности 2 так, чтобы $s_1\subset s_2$. Затем возьмем $s_3 \in \mathcal P(U)$ так, чтобы $s_2\subset s_3$. И т. д. Последним будет взят элемент $s_n=U\in\mathcal P(U)$. Добавим ещё пустое множество $s_0=\varnothing\in\mathcal P(U)$. Таким образом, получим множество $S=\{s_0,\ldots,s_n\}\subset \mathcal P(U)$ мощности $n+1$, упорядоченное по включению: $s_0\subset s_1\subset\cdots\subset s_n$. Все элементы сравнимы, значит порядок линейный.

Но это я только доказал (?), что мощность $S$ может быть $n+1$, а как доказать, что больше быть не может (?) я не знаю. Не подскажите, как добить задачку?

-------
б) В качестве элементов $S$ взять множества одной мощности из $\mathcal P(U)$. Они все не сравнимы между собой. В $\mathcal P(U)$ имеется $\binom n k$ элементов мощности $k$. Наибольшее значение бином. коэффициент имеет, когда $k$ равен половине $n$ (с округлением до целого), т. е. $ \binom {n} {\lfloor {n/2}\rfloor}$. Напр. при $n=10$ таких множеств будет 252.

Но опять та же проблема, что и в а): как доказать, что $|S|$ больше быть не может? А если может, то как его построить?

[Хорхе]

а) если $A\subset B$, то что можно сказать про количества элементов?

б) да, это правильный ответ, но доказывается хитро. Лень писать, мне кажется, на этом форуме обязано было хоть раз появиться.

-- Ср сен 29, 2010 19:03:57 --

Тут, например. Только там слов мало.

[caxap]

Хорхе в сообщении #357363 писал(а):

а) если $A\subset B$, то что можно сказать про количества элементов?

$|A|\leqslant |B|$. Только как это привязать к задаче? Если без всяких ограничений (а, б), то максимальная мощность $S$ равна $2^n$.

-- Ср сен 29, 2010 18:44:42 --

Хорхе в сообщении #357363 писал(а):

Тут, например. Только там слов мало.

Ого, там что-то сложное. Какие-то теоремы, о которых я никогда не слышал. Вообще, книжка (В.Ш.) ориентирована на младшекурсников и для решения задач не нужно дополнительных знаний, выходящих за пределы того, что уже пройдено.
Наверно можно проще.

-- Ср сен 29, 2010 18:51:35 --

б) Может так: если мы уже сделали $S$ как я описал (выбрали из $\mathcal P(U)$ множества одной мощности, причём так, чтобы их было наибольшее число), то добавление ещё одного элемента в $S$ уже не будет удовлетворять условию б): этот элемент либо будет включаться в уже имеющийся элемент, либо наоборот.
Если же набирать элементы разных мощностей, то .... тут надо доказать, что больше $\binom {n}{\lfloor{n/2}\rfloor}$ элементов не получим. С этим пока проблемы...

[Хорхе]

а) хорошо, правильный ответ. Теперь вопрос чуточку сложнее: а что если $A\subset B$ и $A\neq B$?

б) то, что Вы построили в пункте а), называеся максимальной цепью. То, что надо построить в б), называется максимальной антицепью. Посчитайте количество $N$ максимальных цепей двумя способами:
- непосредственно, исходя из того, что все они строятся так же, как та, которую построили Вы
- учитывая, что каждая цепь может проходить только через один элемент антицепи, представьте ее в виде определенной суммы по элементам антицепи
Дальше оцените снизу каждое слагаемое во втором способе одним и тем же числом $m$. Это даст оценку $m\times\text{длина антицепи}\le N$, которая удивительным образом трансформируется в то, что Вы хотите доказать.

[caxap]

(б) интуитивное доказательство)

Если мы берём из $\mathcal P(U)$ в $S$ какой-нибудь элемент $s$, то, чтобы удовлетворить условию б), мы исключаем возможность выбора из $\mathcal P(U)$, с одной стороны, всех $s'$ меньшней мощности таких, что $s'\subset s$ и, с другой стороны, $s''$ большей мощности, таких что $s\subset s''$. Выбор элемента мощности $k$ исключает столько же элементов, сколько и выбор элемента мощности $n-k$. Причём, когда мы приближаемся к "средней" мощности с меньших мощностей, то с увеличением $k$ уменьшается количество исключаемых элементов (а число элементов мощности $k$ растёт). Аналогично, когда мы приближаемся к серединке с бОльших мощностей, то с уменьшением $k$ уменьшается число исключаемых элементов (а число элементов мощности $k$ также растёт). В силу симметрии, лучший для нас случай -- это выбор $\binom{n}{\lfloor n/2 \rfloor}$ элементов средней мощности: их по количеству больше всего, а исключенных элементов меньше всего.

Хорхе, извиняюсь, пока я писал это сообщение, вы уже ответили. Но удалять я его не стал, жалко :)

-- Ср сен 29, 2010 19:59:30 --

Хорхе в сообщении #357414 писал(а):

а) хорошо, правильный ответ. Теперь вопрос чуточку сложнее: а что если $A\subset B$ и $A\neq B$ ?

Ну раз мощности конечные, то $|A|<|B|$. Очень пытаюсь, но увидеть связи с задачей не могу..... (неужели в (а) можно построить множество $S$ мощности больше $n+1$?)

[Хорхе]

а) ну совсем чуть-чуть осталось. Простой вопрос: какова максимальная длина возрастающей последовательности неотрицательных целых чисел, не превышающих $n$?

б) интуитивно оно где-то так и есть, как Вы пишете. Чтобы доказать строго, надо следовать моей подсказке.

[caxap]

Хорхе в сообщении #357423 писал(а):

Простой вопрос: какова максимальная длина возрастающей последовательности неотрицательных целых чисел, не превышающих $n$ ?

$n+1$. А... кажись понял. В этой последовательность всё также, как и со (строгим) включением (раз порядок линеен, то должно быть по не более одному элементу каждой мощности (иначе будут несравнимые элементы)). Значит сделать $|S|$ больше $n+1$ нельзя.

Спасибо.

[caxap]

Хорхе в сообщении #357414 писал(а):

- непосредственно, исходя из того, что все они строятся так же, как та, которую построили Вы

Первый элемент ($\varnothing$) выбирается 1 способом, второй (мощности 1) -- $n$ способов, третий -- $\left\lceil\binom{n}{2}/2\right\rceil$ способов (только в половину второй элемент может включаться; про округление вверх не уверен, я посмотрел на примере $U=\{a,b,c\}$, там ${a}$ может включиться в 2 элемента $\{a,b\},\{a,c\}$. Наверное, и при бОльших $n$ ситуация будет такая же). И т. д.:

$$N=1\cdot n\cdot \left\lceil\frac 12\binom{n}{2}\right\rceil \cdots \left\lceil\frac 12\binom{n}{n-1}\right\rceil \cdot 1 = n\prod_{k=2}^{n-1} \left\lceil \frac 12\binom{n}{k}\right\rceil$$

Хорхе в сообщении #357414 писал(а):

- учитывая, что каждая цепь может проходить только через один элемент антицепи, представьте ее в виде определенной суммы по элементам антицепи

Вот тут не совсем понял. Надо взять каждый элемент (максимальной?) антицепи и посчитать, сколько (максимальных?) цепей через неё проходят? Т. к. всего элементов в максимальной антицепи $M=\binom {n}{\lfloor n/2\rfloor}$, то через каждый элемент проходит $N/M$ макс. цепей.

[Хорхе]

caxap в сообщении писал: писал(а):

третий -- $\left\lceil\binom{n}{2}/2\right\rceil$ способов (только в половину второй элемент может включаться; про округление вверх не уверен, я посмотрел на примере $U=\{a,b,c\}$, там ${a}$ может включиться в 2 элемента $\{a,b\},\{a,c\}$. Наверное, и при бОльших $n$ ситуация будет такая же).

Это не просто неправильно, это бредово. Подумайте, как следует.

[caxap]

Да, извините, ступил Поздно было...

Ну вот давайте на примере множества $U=\{a,b,c,d,e\}$ рассмотрим (я буду для краткости писать просто "abcde"). А потом перейдем к общему случаю. $\mathcal P(U)$ будет содержать:
мощности 0) 1 элемент: $\varnothing$;
мощности 1) 5 элементов: "a","b","c","d","e";
мощности 2) 10 элементов: "ab","ac","ad","ae","bc","bd","be","cd","ce","de";
мощности 3) 10 элементов: "abc","abd","abe","acd","ace","ade","bcd","bce","bde","cde";
мощности 4) 5 элементов: "abcd","abce","abde","acde","bcde";
мощности 5) 1 элемент: "abcde".

Посчитаем количество возможных максимальных цепей: $s_0=\varnothing$ выбираем одним способом, $s_1$ (напр. "a") выбираем 5 способами, $s_2$ (напр. "ab") выбираем 5-1 способами, $s_3$ (напр. "abc") -- 5-2 способами, $s_4$ (напр. "abcd") -- 5-3 способами и $s_5=U$ -- 5-4=1 способом.

В общем случае аналогично: $N=n \cdot (n-1) \cdot (n-2) \cdots 1 = n!$.

-- Чт сен 30, 2010 11:07:16 --

Хорхе в сообщении #357414 писал(а):

учитывая, что каждая цепь может проходить только через один элемент антицепи,

А это откуда следует? Напр. цепь a,ab,abc,abcde и антицепь b,c,de не содержат общего элемента. Если же вы имели ввиду максимальные цепи и антицепи, то, по-моему, здесь нужно знать, какая будет максимальная антицепь, а мы это и пытаемся определить.

-- Чт сен 30, 2010 11:30:07 --

Неужели нельзя проще? Предположим мы выбрали антицепь $S$ из всех элементов $\mathcal P(U)$ средней мощности $\lfloor n/2\rfloor$ (как я писал в первом посте). Надо доказать, что любое отступление приведёт к уменьшению $|S|$.

Просто взять дополнительный элемент из оставшегося $\mathcal P(U)$ нельзя: он обязательно будет включатся в какой-то элемент $S$ или наоборот. Значит, чтобы взять из $\mathcal P(U)$ какой-то другой элемент, надо исключить какой-то (какие-то) элементы из текущего $S$. Но любой элемент $s'\in\mathcal P(U)$ даже ближайщей снизу мощности $\lfloor n/2\rfloor-1$ включается в $n-\lfloor n/2\rfloor = \lceil n/2\rceil$ элементов текущего $S$ (а более низкой мощности -- включается в ещё большее число), а значит, чтобы включить один $s'$ надо исключить $\lceil n/2\rceil-1$ элементов из текущего $S$. Таким образом, включение элемента из $\mathcal P(U)$ мощности меньше средней, в итоге уменьшает мощность $S$.
Аналогичная ситуация с элементами из $\mathcal P(U)$ мощности, больше средней. Значит любое отступление в сторону от текущего $S$ приведет к уменьшению его мощности. А значит максимум и будет, когда $S$ состоит из всех элементов $\mathcal P(U)$ средней мощности.

Такое доказательство годится? (Ув. Хорхе, если честно, по мне лучше вылизать данное доказательство, если оно имеет верное направление, чем то, на которое направляете меня вы. Просто потому, что в своём я хоть что-то понимаю. Но если мой путь никуда не ведёт, то буду следоватать вашему методу )

[Null]

Вы не учли что возможно удалив несколько элементов появиться возможность добавить больше новых элементов.

[Хорхе]

caxap в сообщении #357582 писал(а):

Хорхе в сообщении #357414 писал(а):

учитывая, что каждая цепь может проходить только через один элемент антицепи,

А это откуда следует? Напр. цепь a,ab,abc,abcde и антицепь b,c,de не содержат общего элемента. Если же вы имели ввиду максимальные цепи и антицепи, то, по-моему, здесь нужно знать, какая будет максимальная антицепь, а мы это и пытаемся определить.

Да, я неправ в том, что цепь и антицепь обязаны пересекаться. Впрочем, написанное мною неравенство остается правильным, поскольку через два элемента антицепи цепь точно не может проходить.

caxap в сообщении #357582 писал(а):

Такое доказательство годится? (Ув. Хорхе, если честно, по мне лучше вылизать данное доказательство, если оно имеет верное направление, чем то, на которое направляете меня вы. Просто потому, что в своём я хоть что-то понимаю. Но если мой путь никуда не ведёт, то буду следоватать вашему методу )

Я конечно, понимаю, что из своего рассуждения легче конфетку слепить, но это может затянуться надолго.

Направление сложно назвать верным (а Ваше рассуждение сложно назвать доказательством). Верна, как я уже говорил в прошлом посте, интуиция. А от интуиции до доказательства иногда очень далеко (временами вообще бесконечно далеко по причине ошибочности интуиции: немало математических фактов противоречат интуиции).

[caxap]

Хорхе в сообщении #357615 писал(а):

поскольку через два элемента антицепи цепь точно не может проходить.

Да, с этим не поспоришь. Но не могли бы вы пояснить

Хорхе в сообщении #357414 писал(а):

- учитывая, что каждая цепь может проходить...

Я что-то не догоняю. Что там за сумма?

[Хорхе]

Давайте сперва ответим на вопрос, сколько всего есть максимальных цепей.

Не забывайте про порядок и про то, как именно эти цепи строятся.

[caxap]

Хорхе
Разве ответ $N=n!$ неверный? Если да, то где я мог ошибиться?