Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 7 ] |
|
Автор | Сообщение | |
---|---|---|
username |
|
|
речь о беспорядках арифметической прогрессии, а точнее о их "максимизации". мера беспорядка тут определяется как сумма модулей разность между элементами беспорядка и их индексами. например, имеем последовательность a: 1 2 3 4 один из беспорядков был бы b_k: 2 1 4 3 модули разностей между b_k[i] и i: 1 1 1 1 сумма модулей разностей: 4. задача заключается в нахождении этого максимума и определении количества таких максимальных беспорядков. в общем виде: имеем арифметическую прогрессию a = {1, 2, 3 ... N} b_k - один из беспорядков: b_k[i] != i, для любого i = 1 ... N. требуется определить: max( SUM (|b_k[i] - i|) ) = ?, из всех возможных беспорядков b_k, k = 1 ... K = !N - число возможных беспорядков, i = 1 ... N. был бы очень благодарен, если бы кто-то смог бы подсказать, в каком хотя бы направлении копать, ибо моего дилентантизма для решения не хватает. всем заранее огромное спасибо! |
||
Вернуться к началу | ||
Avgust |
|
|
Думаю, что в данном случае 4321 даст максимальный показатель 8. Тут наверное и алгоритм прослеживается.
|
||
Вернуться к началу | ||
Sonic |
|
|
1-й вариант: брать последовательность [math]n...21[/math]
2-й - для [math]k[/math]-го члена брать [math]k+n/2[/math]. Похоже, что максимумы совпадают. Наверное, имеет смысл вычислить для нескольких [math]n[/math] максимумы опытным путем, посмотреть на них. Количество максимальных беспорядков явно неединичное. Надо бы посчитать.... З.Ы. Для набора формул используйте тег math и редактор формул в окошке редактирования: viewtopic.php?f=5&t=3174 upd1: Обозначим перестановку буквой [math]\pi[/math], ее длина - [math]n[/math], отклонение [math]R(\pi):=\sum\limits_{k=1}^n|\pi(k)-k|[/math]. Тогда [math]|\pi(k)-k|[/math] тривиально оценивается сверху, откуда следует тривиальная оценка для [math]R(\pi)[/math].(дальше было вранье...) upd2: количество перестановок [math]\pi[/math] со значением [math]R=R(\pi)[/math] обозначим [math]N(R)[/math]. Тогда [math]N(2m+1)=0[/math] (интересно, почему), [math]N(0)=1, N(2)=n-1[/math]. Ну это я просто так... |
||
Вернуться к началу | ||
Sonic |
|
|
upd3: Надо писать не [math]N(R)[/math], а [math]N_n(R)[/math].
Для [math]n=1[/math] [math]R_{\max}=0, N_1(2)=1[/math]. Для [math]n=2[/math] [math]R_{\max}=2, N_2(2)=1[/math]. Для [math]n=3[/math] [math]R_{\max}=4, N_3(2)=3[/math]. Для [math]n=4[/math] [math]R_{\max}=8, N_4(2)=4[/math]. Для [math]n=5[/math] [math]R_{\max}=12, N_5(2)=20[/math]. Кажется, это не очень легкая задача. М.б. [math]N_n(R_{\max})\sim Cn!, C-?[/math], вообще [math]N_n(R)[/math] сначала возрастает до максимума, потом убывает, распределение несимметрично, максимум лежит справа. upd4: последовательность числа максимумов есть в OEIS: http://oeis.org/A062870 В частности: Цитата: Conjecture: a(n) = (n/2)!^2 if n is even else n*((n-1)/2)!^2 С доказательством maxala, в нем есть и формулы для [math]R_{\max}[/math]. Можно попытаться что-то у него спросить...upd5: А не! Доказательство простое! Наверное, Вам этого хватит... Последний раз редактировалось Sonic 06 окт 2012, 16:08, всего редактировалось 1 раз. |
||
Вернуться к началу | ||
username |
|
|
|
||
Вернуться к началу | ||
Sonic |
|
|
Там обозначение мультимножества необычное: [math]a^b[/math] означает элемент [math]a[/math] [math]b[/math] раз.
|
||
Вернуться к началу | ||
username |
|
|
да, конечно, я понял.
еще раз большое спасибо! очень помогли! |
||
Вернуться к началу | ||
[ Сообщений: 7 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
О делимости числа беспорядков | 1 |
375 |
31 дек 2016, 17:51 |
|
Максимизация излишка потребителя
в форуме Экономика и Финансы |
1 |
330 |
26 июн 2020, 11:55 |
|
Максимизация соотношения риск/доходность | 2 |
332 |
12 авг 2017, 16:26 |
|
Максимизация площади под графиком при заданных условиях
в форуме Интегральное исчисление |
2 |
241 |
25 июн 2020, 19:26 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |