2014 dxdy logo

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

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


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


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

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

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

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

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



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


14/02/07
2648
Правильный, прошу прощения, не заметил в гуще всего остального.

Хорошо.

Теперь такой вопрос: сколько цепей проходит через данное $k$-элементное множество $A$ (Вы можете представить такую цепь как объединение двух: той, что из $\varnothing$ приходит в $A$, и той, что из $A$ приходит $U$)?

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


07/01/10
2015
Ну раз всего макс. цепей $n!$, а всего $k$-элементных множеств $\binom n k$, то через каждое $k$-элементное множество проходит $n!\big/ \binom n k$ макс. цепей.

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


12/08/10
1650
Ответ правильный,но не обоснованно почему через каждое $k$-элементное множество проходит одинаковое количество максимальных цепей.

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


07/01/10
2015
Null
В силу симметрии все $k$-элементные множества равнозначны.

(Доказательство)

Предположим, что $k$-элементных множеств ($\in \mathcal P(U)$), содержащих элемент $u_1\in U$ больше, чем тех, которые содержат $u_2\in U$. Выполним биекцию $\varphi: U\to U$, которая переставит эти элементы ($u_1\mapsto u_2$ и наоборот; остальные элементы перейдут в себя). С одной стороны, теперь больше должно стать количество множеств, содержащих $u_2$, чем содержащих $u_1$. А с другой стороны -- ничего измениться не должно, т. к. $U=\varphi(U)$ и $\mathcal P(U)=\mathcal P(\varphi(U))$. Противоречие.

Не знаю, можно ли считать это доказательством, но по-моему, это настолько очевидный факт, что доказывать его не нужно (по крайней мере в рамках того учебника, из которого эта задачка).

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


14/02/07
2648
Это прекрасно. Рассуждения на тему симметрии всесильны, потому что они верны.

Теперь вопрос: какое наименьшее (по $k$) значение принимает $n!/{n\choose k}$?

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


07/01/10
2015
Когда $k=0$ (или $k=n$), то $f(n,k):=n!\big/ \binom nk=k!\, (n-k)!=n!$. Если будем увеличивать $k$ (до середины $\lfloor n/2\rfloor$), то $f(n,k)$ будет уменьшаться (увеличивая $k$, мы "добавляем" множитель в $k!$ ценой потери бОльшего множителя из $(n-k)!$). Поскольку $f(n,k)=f(k,n)$, то такая же ситуация будет при уменьшении $k$ от $n$ до $\lfloor n/2\rfloor$. Значит минимум будет как раз посрединке, при $k=\lfloor n/2\rfloor$, т. е. $f(n,k)=f(\lceil n/2\rceil,\lfloor n/2\rfloor)=\lceil n/2\rceil !\, \lfloor n/2\rfloor!$.

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


14/02/07
2648
Чудесно. Теперь напишите неравенство из этого моего поста, и Вы в дамках!

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


07/01/10
2015
Получается $\lceil n/2\rceil !\, \lfloor n/2\rfloor! \cdot \ell \leqslant n!$ и
$$\ell \leqslant \frac{n!}{\lceil n/2\rceil !\, \lfloor n/2\rfloor!} = \binom n {\lfloor n/2\rfloor}$$
То есть мы доказали, что больше этого $\ell$ быть не может, а равенства мы знаем как добиться (см. первый пост). Всё, конец?

В формулках всё, конечно, здорово выходит, но я пока не до конца разобрался, откуда берётся то неравенство...

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


14/02/07
2648
Всё, конец.

Насчет "не до конца разобрался", есть замечательное высказывание (тут у кого-то в подписи увидел):
Дж. фон Нейман писал(а):
В математике вещи не понимают. К ним привыкают.

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


07/01/10
2015
Хорхе в сообщении #357702 писал(а):
В математике вещи не понимают. К ним привыкают.

Не, ну так нельзя. Надо понять.

Через каждый элемент максимальной антицепи длины $\ell$ может проходить $k!\,(n-k)!$ макс. цепей, где $k$ -- мощность рассматриваемого элемента антицепи. Мы знаем, что всего макс. цепей $n!$, значит $\ell \cdot k!\,(n-k)! \geqslant n! \iff \ell \geqslant \binom n k$.

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


14/02/07
2648
caxap в сообщении #357705 писал(а):
Мы знаем, что всего макс. цепей $n!$, значит $\ell \cdot k!\,(n-k)! \geqslant n! \iff \ell \geqslant \binom n k$.

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

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


07/01/10
2015
Хорхе в сообщении #357712 писал(а):
Только вот неравенство в другую сторону, а так правильно.

:shock: Странно. Я уже собирался исправлять, а вы ответили. Ведь $k$ -- это мощность элемента $s$ макс. антицепи $S$, а суммирование по элементам и ведётся, т. е. $k$ связанная переменная. Она из суммы выйти не смогла бы.

Ещё раз попробую. Через каждый $s\in S$ может проходить $|s|!\, (n-|s|)!$ макс. цепей. Проссумируем по всем элементам $S$:
$$\sum_{s\in S} |s|!\,(n-|s|)! \geqslant |S|\cdot \lceil n/2\rceil !\, \lfloor n/2 \rfloor !$$
С другой стороны эта сумма $\geqslant n!$, т. е. всех макс. цепей. А откуда вышло, что $|S|\cdot \lceil n/2\rceil !\, \lfloor n/2 \rfloor !\leqslant n!$ ?

-- Чт сен 30, 2010 19:47:20 --

Пардон, всё понял. Эта сумма $\leqslant n!$. Извиняюсь за тупость.

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


07/01/10
2015
Ещё задачки из того же параграфа:

88. Сколько существует различных линейных порядков на множестве из $n$ элементов?

Каждому линейному порядку $a_1\leqslant a_2\leqslant\ldots\leqslant a_n$ можно поставить в соответствите последовательность $(a_1,a_2,\ldots,a_n)$. Таких последовательностей $n\cdot (n-1)\cdots 1=n!$ (по комбинаторному правилу умножения), а значит и линейных порядков столько же.

89. Докажите, что всякий частичный порядок на конечном множестве можно продолжить до линейного (если $x\leqslant y$ в исходном порядке, то и в новом должно быть так же).

Обозначим это множество $A$ и пусть в нём $n$ элементов. Рассмотрим множество $B\subset A$ тех элементов из $A$, которые не сравнимы. Введём порядок на $B$ следующим образом: возьмём любой элемент $b_1$ из $B$, затем возьмём второй $b_2$ и положим $b_1\leqslant' b_2$, затем третий $b_3$ и положим $b_2\leqslant' b_3$ и т. д., пока на всём множестве $B$ не получится линейный порядок.
На всех сравнимых элементах $A$ положим $\leqslant' = \leqslant$.
Далее возьмём максимальный элемент $a_n$ из $A$ и положим $a_n\leqslant' b_1$.

Таким образом, все элементы получились сравнимы, значит порядок линеен.

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


14/02/07
2648
Первая решена правильно.

А вот тут:
caxap в сообщении #357774 писал(а):
Рассмотрим множество $B\subset A$ тех элементов из $A$, которые несравнимы.

непонятки. Вот если чум такой: $A=\{a,b,c\}$, $a<b$ --- единственное строгое сравнение, то чему равно $B$?

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


07/01/10
2015
Хорхе в сообщении #357777 писал(а):
Вот если чум такой: $A=\{a,b,c\}$, $a<b$ --- единственное строгое сравнение, то чему равно $B$?

Ага, ошибся.

Попытка номер два. Для начала примем $\leqslant'=\leqslant$ на всех сравнимых элементах $A$.

Далее возьмём максимальный элемент $a_n\in A$ и рассмотрим множество $B$ тех элементов из $A$, которые не сравнимы с $a$. Внутри $B$ вводим порядок $\leqslant'$ так же, как я вводил его для $B$ в прошлом посте. Переносим этот порядок в множество $A$ и полагаем $a_n\leqslant' b_1$. Если в $A$ остались несравнимые элементы, переходим к началу абзаца и делаем те же шаги. Раз множество конечное, то рано или поздно из цикла выйдем. А раз выйдем, то значит порядок станет линейным.

-- Чт сен 30, 2010 21:33:27 --

В приведённом вами примере за один цикл получаем лум: $a <' b \leqslant c$, где $a <' b \iff a\leqslant' b \land a\neq b$.

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

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



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

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


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

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