2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5, 6  След.
 
 Верещагин, Шень. Эквивалентность и порядок
Сообщение29.09.2010, 17:06 
Заслуженный участник
Аватара пользователя


07/01/10
2015
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|$ больше быть не может? А если может, то как его построить?

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение29.09.2010, 18:01 
Заслуженный участник
Аватара пользователя


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

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

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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение29.09.2010, 18:36 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Хорхе в сообщении #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}$ элементов не получим. С этим пока проблемы...

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение29.09.2010, 19:42 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение29.09.2010, 19:58 
Заслуженный участник
Аватара пользователя


07/01/10
2015

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

Если мы берём из $\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$?)

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение29.09.2010, 20:04 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение29.09.2010, 20:14 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Хорхе в сообщении #357423 писал(а):
Простой вопрос: какова максимальная длина возрастающей последовательности неотрицательных целых чисел, не превышающих $n$ ?

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

Спасибо.

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение29.09.2010, 22:14 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Хорхе в сообщении #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$ макс. цепей.

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение29.09.2010, 23:17 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 10:50 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Да, извините, ступил :oops: Поздно было...

Ну вот давайте на примере множества $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)$ средней мощности.

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 13:27 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 14:18 
Заслуженный участник
Аватара пользователя


14/02/07
2648
caxap в сообщении #357582 писал(а):
Хорхе в сообщении #357414 писал(а):
учитывая, что каждая цепь может проходить только через один элемент антицепи,

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

Да, я неправ в том, что цепь и антицепь обязаны пересекаться. Впрочем, написанное мною неравенство остается правильным, поскольку через два элемента антицепи цепь точно не может проходить.
caxap в сообщении #357582 писал(а):
Такое доказательство годится? (Ув. Хорхе, если честно, по мне лучше вылизать данное доказательство, если оно имеет верное направление, чем то, на которое направляете меня вы. Просто потому, что в своём я хоть что-то понимаю. Но если мой путь никуда не ведёт, то буду следоватать вашему методу :wink: )

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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 14:24 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Хорхе в сообщении #357615 писал(а):
поскольку через два элемента антицепи цепь точно не может проходить.

Да, с этим не поспоришь. Но не могли бы вы пояснить
Хорхе в сообщении #357414 писал(а):
- учитывая, что каждая цепь может проходить...

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 15:13 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 15:16 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 81 ]  На страницу 1, 2, 3, 4, 5, 6  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group