Какое наименьшее значение может принимать выражение $$(x_1-x_2)^2+(x_2-x_3)^2+...+(x_{n-1}-x_n)^2+(x_n-x_1)^2,$$ если $%x_1,x_2,...,x_n -$% попарно разные целые числа?

задан 15 Фев '16 18:01

перемечен 15 Фев '16 18:06

Trumba's gravatar image


74118

Минимум вроде бы достигается когда взять, например, набор $%1,3,5,7,6,4,2$%: Но, непонятно как доказать.

(16 Фев '16 19:19) Роман83
1

@Роман83: у меня есть примерная схема доказательства, основанная на том, что если где-то разрыв между числами длиной 3 или более, то сумму квадратов можно уменьшить. Судя по всему, это верно, но надо как следует это дело оформить.

(16 Фев '16 19:24) falcao
10|600 символов нужно символов осталось
1

Можно считать, что все числа идут подряд: в противном случае возможно очевидное "уплотнение". Рассматриваем перестановку чисел от $%1$% до $%n$%.

Для начала докажем, что $%1$% и $%2$% в цикле идут рядом. Если это не так, то цикл имеет вид $%1\to i\to\cdots\to2\to j\to\cdots\to1$%, где $%i,j\ge3$%. Удобно представить себе числа, расположенные по окружности. Тогда заменяем цикл на "восьмёрку", разрывая связи между $%1$%, $%i$% и между $%2$%, $%j$%, беря вместо этого $%1\to2\to\cdots\to i\to j\to\cdots\to1$% (числа от $%2$% до $%i$% идут теперь в обратном порядке). Сумма квадратов уменьшилась, так как $%(i-1)^2+(j-2)^2 > (i-j)^2+(2-1)^2$%.

Теперь, поскольку $%1$% и $%2$% должны быть соседями, удаляем их из цикла, и ищем перестановку чисел, начинающуюся с $%1$% и кончающуюся на $%2$% с минимальной суммой квадратов. Будем доказывать, что оптимальное значение общей суммы квадратов равно $%4n-6$% при $%n\ge2$%. Попутно станет ясно, как выглядит оптимальный цикл. База индукции очевидна.

Достаточно проверить, что за $%1$% идёт $%3$%. Тогда изъятие первого "звена" приводит к задаче для перестановки чисел от $%2$% до $%n$%, и понятно, что сумма квадратов увеличивается на $%4$%. При $%n=3$% всё ясно; полагаем $%n\ge4$%. Рассматриваем два случая.

а) $%1\to i\to\cdots\to3\to j\to\cdots\to2$%, где $%3$% и $%2$% не соседствуют. Здесь $%i,j\ge4$%. Цепочку можно улучшить, взяв вместо неё $%1\to3\to\cdots\to i\to j\to\cdots\to2$%. Вместо $%(i-1)^2+(j-3)^2$% стало $%(i-j)^2+4$%, то есть произошло уменьшение, что легко проверяется непосредственно.

б) $%1\to i\to\cdots\to3\to2$%, где $%3$% и $%2$% соседствуют. Здесь берём $%1\to3\to\cdots\to i\to2$%, и вместо $%(i-1)^2+1$% стало $%(i-2)^2+4$%, то есть произошло уменьшение за счёт $%i\ge4$%.

ссылка

отвечен 17 Фев '16 17:52

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×160
×50

задан
15 Фев '16 18:01

показан
478 раз

обновлен
17 Фев '16 17:52

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru