Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: "максимизация" беспорядков
СообщениеДобавлено: 05 окт 2012, 23:33 
Не в сети
Начинающий
Зарегистрирован:
05 окт 2012, 23:29
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
друзья, помогите!
речь о беспорядках арифметической прогрессии, а точнее о их "максимизации". мера беспорядка тут определяется как сумма модулей разность между элементами беспорядка и их индексами.
например,
имеем последовательность 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.

был бы очень благодарен, если бы кто-то смог бы подсказать, в каком хотя бы направлении копать, ибо моего дилентантизма для решения не хватает.
всем заранее огромное спасибо!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: "максимизация" беспорядков
СообщениеДобавлено: 06 окт 2012, 01:16 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 13534
Откуда: Москва
Cпасибо сказано: 1290
Спасибо получено:
3616 раз в 3175 сообщениях
Очков репутации: 678

Добавить очки репутацииУменьшить очки репутации
Думаю, что в данном случае 4321 даст максимальный показатель 8. Тут наверное и алгоритм прослеживается.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: "максимизация" беспорядков
СообщениеДобавлено: 06 окт 2012, 13:58 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
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]. Ну это я просто так...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: "максимизация" беспорядков
СообщениеДобавлено: 06 окт 2012, 15:12 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
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 раз.
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: "максимизация" беспорядков
СообщениеДобавлено: 06 окт 2012, 15:48 
Не в сети
Начинающий
Зарегистрирован:
05 окт 2012, 23:29
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
огромнейшее спасибо!
вот тут и доказательство есть http://oeis.org/A062870/a062870.txt

класс!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: "максимизация" беспорядков
СообщениеДобавлено: 06 окт 2012, 16:09 
Не в сети
Оракул
Зарегистрирован:
09 сен 2011, 12:29
Сообщений: 760
Cпасибо сказано: 16
Спасибо получено:
221 раз в 185 сообщениях
Очков репутации: 89

Добавить очки репутацииУменьшить очки репутации
Там обозначение мультимножества необычное: [math]a^b[/math] означает элемент [math]a[/math] [math]b[/math] раз.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: "максимизация" беспорядков
СообщениеДобавлено: 06 окт 2012, 16:15 
Не в сети
Начинающий
Зарегистрирован:
05 окт 2012, 23:29
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
да, конечно, я понял.
еще раз большое спасибо!
очень помогли!

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 7 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
О делимости числа беспорядков

в форуме Интересные задачи участников форума MHP

Boris Skovoroda

1

375

31 дек 2016, 17:51

Максимизация излишка потребителя

в форуме Экономика и Финансы

lenyapetrov2021

1

330

26 июн 2020, 11:55

Максимизация соотношения риск/доходность

в форуме Исследование операций и Задачи оптимизации

wormeer

2

332

12 авг 2017, 16:26

Максимизация площади под графиком при заданных условиях

в форуме Интегральное исчисление

max_korostelev

2

241

25 июн 2020, 19:26


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved