2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу 1, 2, 3  След.
 
 по следам перестановочного неравенства
Сообщение14.02.2009, 03:34 
Модератор
Аватара пользователя


11/01/06
5360
Пусть $S_n$ - это множество всех перестановок чисел $\{1,2,\dots,n\}$.
Найдите значение
$$\min_{\pi,\sigma,\tau\in S_n} \sum_{j=1}^n \pi(j)\cdot \sigma(j)\cdot\tau(j)$$
как функцию от $n$.

 Профиль  
                  
 
 
Сообщение14.02.2009, 17:09 
Заслуженный участник
Аватара пользователя


14/02/07
2648
Могу посчитать максимум :)

 Профиль  
                  
 
 
Сообщение14.02.2009, 17:24 
Заслуженный участник
Аватара пользователя


15/10/08
7392
Просто напросто ничего не понял в обозначениях.

 Профиль  
                  
 
 
Сообщение14.02.2009, 17:49 
Модератор
Аватара пользователя


11/01/06
5360
Утундрий
см. что такое перестановка в википедии.
если непонятно обозначение с минимумом, то словесное описание такое: для заданного $n$ нужно выбрать три перестановки $\pi$, $\sigma$ и $\tau$ порядка $n$ так, чтобы указанная сумма была минимально возможной. Нужно выразить это минимальное возможное значение как функцию от $n$.

 Профиль  
                  
 
 
Сообщение14.02.2009, 18:05 
Заслуженный участник
Аватара пользователя


15/10/08
7392
Непонятно обозначение с суммой. Если точкой обозначена композиция, то получается, что Вы там перестановки суммируете, что ли? И кто такой индекс $j$ ? По какому принципу отбираются тройки элементов симметрической груммы, входящие в сумму?

 Профиль  
                  
 
 
Сообщение14.02.2009, 18:13 
Модератор
Аватара пользователя


11/01/06
5360
Точка - это обычное произведение. Индекс $j$ бежит от 1 до $n$, для каждого $j$ берется произведение $j$-х элементов всех трех перестановок, и все это суммируется.

 Профиль  
                  
 
 
Сообщение14.02.2009, 18:16 


29/10/07
71
Ялта
Для случая двух постановок нетрудно показать, что искомый максимум достигается, когда соответствующие подстановки совпадают.

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

 Профиль  
                  
 
 
Сообщение14.02.2009, 18:22 
Модератор
Аватара пользователя


11/01/06
5360
Sinus
Результат о двух перестановках - это и есть перестановочное неравенство. Из него легко следует решение для аналогичной задачи с максимумом.
Но в этой спрашивается про минимум.

 Профиль  
                  
 
 
Сообщение14.02.2009, 18:38 


29/10/07
71
Ялта
Извиняюсь за свою невнимательность...

Опять же, для двух перестановок минимум достигается когда их (перестановок) сумма постоянна и равна n+1. Однако для данной задачи не видно как реализовать такие идеи.

Интересная задача.

 Профиль  
                  
 
 
Сообщение14.02.2009, 19:39 
Заслуженный участник


09/02/06
4339
Москва
Задачу на максимум maxal не стал бы задавать. Для любого количества произведений максимум достигается на тождественных перестановках, соответственно для 3-х сумма кубов равно $S_{max}=\frac{n^2(n+1)^2}{4}$.
Пусть $n=3k, \tau(i)=i, \pi(i)=2k+1-i,i\le k,$
$\pi(i)=i+k,k<i\le 2k,\pi(i)=n+1-i,i>2k, \sigma(i)=\pi^2(i)$.
Тогда $S=3\sum_{i=1}^k i(2k+1-i)(3k+1-i)=\frac{n(n+3)(19n^2+45n+18)}{4*81}$.
Если $n=3k+1$ сделаем неподвижную точку в интервале [k+1,2k+1] в остальном определим так же.Т.е. $\tau(i)=i,\pi(i)=2k+2-i,i\le k+1,$
$\pi(i)=k+i,k+1<i<2k+2,\pi(i)=i+k,i\ge 2k+2,\sigma(i)=\pi^2(i)$.
Тогда $S=(k+1)^3+3\sum_{i=1}^k i(2k+2-i)(3k+2-i)=(k+1)^3+\frac{k(k+1)}{4}[19k^2+37k+16]$.
В случае $n=3k+2$ надо брать две неподвижные точки и определить $\tau(i)=i,\pi(i)=2k+2-i,i\le k+1$
$\pi(i)=i+k+1,k+1<i<2k+2,\pi(2k+2)=2k+2, \pi(i)=3k+3-i,i>2k+2$
$\sigma(i)=\pi^(i),i\not =k+1,2k+2,\sigma(2k+2)=k+1,\sigma(k+1)=2k+2.$
Вроде на них достигается минимум.

 Профиль  
                  
 
 
Сообщение14.02.2009, 19:57 
Модератор
Аватара пользователя


11/01/06
5360
Руст
Твои формулы начинают врать с $n=7$. Для $n=7$ минимум равен 271, а у тебя получается 276.

 Профиль  
                  
 
 
Сообщение14.02.2009, 21:15 
Заслуженный участник


09/02/06
4339
Москва
А для случая $n=3k$ правильны?.

 Профиль  
                  
 
 
Сообщение14.02.2009, 21:44 
Модератор
Аватара пользователя


11/01/06
5360
Руст
Для $n=3k$ тоже начинаются проблемы, начиная с $n=9$ (у тебя получается 654, а должно быть 642).

 Профиль  
                  
 
 
Сообщение14.02.2009, 22:25 
Заслуженный участник


09/02/06
4339
Москва
Я привлекал только интуитивные соображения для минимизации. Похоже хорошей формулы для минимального значения не существует.

 Профиль  
                  
 
 
Сообщение15.02.2009, 08:40 
Заслуженный участник


09/02/06
4339
Москва
Приведу соображения, приводящие к вышеуказанным формулам.
Введём метрику в группе перестановок $s(n)$: $ro (sigma,sigma')=||\sigma^{-1}\sigma'||$, где норма равно $||\sigma||=\sum_i (l_i-1),\sigma=(x_1,...,x_{l_1})(x_{m_1+1},...,x_{m_2}),...$
$m_1=l_1,m_{i}=m_{i-1}+l_i$. Соответственно расстояние между $\sigma,\sigma'$ равно 1, если найдётся i,j, что $\sigma'(k)=\sigma(k),k\not =i,j, \sigma'(i)=\sigma(j),\sigma'(j)=\sigma(i)$.
$$S(\pi,\sigma,\tau)=\sum_{j=1}^n\pi(j)\sigma(j)\tau(j)$$
принимает локальный минимум, если $$S(\pi',\sigma',\tau')>S(\pi,\sigma,\tau)$$ для любых перестановок с условием $ro(\pi,\pi')+ro(\sigma,\sigma')+ro(\tau,\tau')=1$.
Указанные перестановки дают локальный минимум.

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

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



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

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


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

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