Задача о минимуме/максимуме скалярного произведения

Задача:

Необходимо найти минимальную/максимальную суммы попарных произведений для двух заданных упорядоченных наборов чисел.

Решение

Скалярным произведением двух упорядоченных последовательностей чисел будем называть число [math]S = x_1 y_1 + x_2 y_2 + \ldots + x_m y_m[/math]

Теорема (о минимуме/максимуме скалярного произведениях):

Минимум скалярного произведения достигается при сопоставлении возрастающей последовательности [math]x_1 \ldots x_m[/math] и убывающей последовательности [math]y_1 \ldots y_m[/math]. При сопоставлении возрастающей [math]y_1 \ldots y_m[/math] достигается максимум.

Доказательство:

[math]\triangleright[/math]

Будем считать, что последовательность [math]x_i[/math] отсортирована по возрастанию. Покажем, что если существуют пары чисел [math](x_i, y_i)[/math] и [math](x_j, y_j)[/math], такие что [math]x_i \lt x_j[/math] и [math]y_i \lt y_j[/math], то скалярное произведение можно уменьшить, поменяв местами [math]y_i[/math] и [math]y_j[/math]. Так как в нашем случае [math](x_j - x_i)(y_j - y_i) \gt 0[/math], то [math]x_i y_i + x_j y_j \gt x_j y_i + x_i y_j[/math], а следовательно данное скалярное произведение не является минимальным. Проделав такую замену для всех [math]y_i \lt y_j[/math] получим отсортированную по убыванию последовательность [math]y_i[/math], и скалярное произведение такой пары последовательностей будет минимальным. Аналогично для получения максимума во всех парах чисел [math](x_i, y_i)[/math] и [math](x_j, y_j)[/math], таких что [math]x_i \lt x_j[/math] и [math]y_i \gt y_j[/math] нужно менять местами [math]y_i[/math] и [math]y_j[/math]. В результате получится отсортированная по возрастанию последовательность, и скалярное произведение в таком случае будет максимальным.

[math]\triangleleft[/math]

Данная теорема нашла себе практическое применение в теории матроидов и расписаний.

См. также

• Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП
• Теорема Кэли
• Матричное представление перестановок

Источники информации

• Романовский И. В. Дискретный анализ. — 3-е изд. — С. 320 — ISBN 5-7940-0114-3.