Нахождение наименьшей средней разницы в классе

Question

Учитывая класс с русскими мальчиками и русскими девушками, в которых девочки получили оценки p1, ..., pn, а мальчики получили оценки s1, ..., sn на экзамене, найти пару девочек-мальчиков таким образом, чтобы минимизировать среднее различие между классами в парах. Например, если p1 = 30, p2 = 60, s1 = 50, s2 = 90, мы должны пара № 1 с мальчиком № 1 (разница в 20 очков) и девушка № 2 с мальчиком № 2 (разница 30 очков) и мы получим минимальную среднюю разницу (30 + 20)/2 = 25.

Докажите, что оптимальным является следующий алгоритм: Пара девушка с самым низким уровнем для мальчика с самым низким классом. Тогда пара девушки с второй низшей ступени к мальчику с второй самой низкой ступени и т.д.

---

В моем решении, я попытался с помощью жадного свойство выбора (показывая, что существует оптимальное решение, в котором определенный элемент находится в растворе, а затем с помощью индукции доказать, что все элементы находятся в оптимальном решении):

Пусть A1 < = ... < = Ап сортов девушки отсортированность и B1 < = ... < = Bn - сортировка мальчиков.

Претензия - существует оптимальное решение, которое включает в себя пару A1-B1 (мальчик с самым низким классом в паре с девушкой с самым низким классом).

Доказательство. Предположите противным, что утверждение неверно. Поэтому ни одно оптимальное решение не включает A1-B1 в качестве пары. Предположим, что A1-Bi (i> 1) и B1-Aj (j> 1) являются парами в решении. Мы знаем, что A1 < = Aj и B1 < = Bi. Как мне продолжить?

Заранее спасибо.

Answer 1

ОК, я нашел что-то, основанное на некоторых геометрических наблюдениях.
Скажем, у вас на данный момент всего 4 цифры: a1 < = a2 и b1 < = b2 (0).

| a1-b1 | + | a2-b2 | < = | a1-b2 | + | a2-b1 | (1)

В этом случае мы хотим проверить, является ли (1) истинным.

Я перепишем (1) на основе очевидных отношений эквивалентности:

(| a1-b1 | + | a2-b2 |)^2 < = (| a1-b2 | + | a2-b1 |)^2 (2)

-2 * a1 * b1 -2 * a2 * b2 < = -2 * a1 * b2 -2 * a2 * b1 (3)

Должен ли я объяснить, как я получил от (2) до (3)? Наверное, нет.

Тогда мы получим:

a1 * b1 + a2 * b2> = a1 * b2 + a2 * b1 (4)

a1 (b1-b2)> = a2 * (b1-b2) (5)

a1 (b1-b2), - а2 * (b1-b2)> = 0 (6)

a1 (b1-b2) + а2 * (b2-b1)> = 0 (7)

Но (5), очевидно, верно, потому что b1-b2 < = 0 и a1 < = a2 (см. (0)).

Это строгое доказательство для N = 2.

Моя кишка говорит мне, что это должно быть обобщено как-то
довольно легко для случая N. Может быть, мы можем попробовать
индукции отсюда (видев это (1), (2), (3), и т.д.).

Геометрически, вы можете себе представить, что Ai и Bj в качестве точки
на два параллельных числовом Линекс (ось А, ось B). Одна конфигурация сопряжения
определяется путем соединения парных
точек из A и B с сегментами. Ваше заявление в основном
говорит, что оптимальное сопряжение является тот, в котором нет двух
сегментов (Ai, Bj) не пересекаются друг с другом (они могут пересекаться с
друг друга/в оптимальном решении/но не могут пересекаться друг с другом) ,
Справа?

Теперь, если мы делаем то же самое (что я сделал для N = 2),
для любого N, вы получите этот вопрос: «
a1 (b1-Bi1) + a2 (В2 bi2) + a3 (b3-bi3) + ... + aN * (bN-biN)> = 0 (4 ')
true ", где i1, i2, ..., iN - любая перестановка (1, 2, ..., N),
и при условии, что a [i] < = a [i + 1] и b [i] < = b [i + 1] для каждого i.

Теперь мы делаем индукцию по N, чтобы доказать (4 ').
Предположим, что (4 ') верно для N и для всех K таких, что K < N.
Добавить еще два числа в A и B. Скажем aN + 1 и bN + 1.
Предположим, что они вставлены в положения s1 (в A) и s2 (in B)
в их соответствующих последовательностях SORTED (A, B). Скажем s1 < = s2
(обратный случай аналогичен).Итак, теперь as1 = aN + 1 и bs2 = bN + 1,
, но s1 и s2 являются их реальными индексами в НОВЫХ отсортированных последовательностях.

Но теперь доказать (4 «) для N + 1 превращается в вопрос
доказав его для N = 2, так как только эти условия (из (4»))
материи, когда мы делаем шаг от N до N + 1.

as1 * (BS1 - БС2) + as2 * (БС2 - BS1)> = 0 (7')
и, как мы видели, это верно для N = 2 (см (7) выше).

Для других условий N-1 (которые остаются от (4)), получаем, что
неравенство (4 ') справедливо в силу предположения из индукции (что
верно для N-1). Таким образом, из истины для 2 и N-1 мы получили истину для N + 1.
Надеюсь, вы поймете, как я это сделал. На бумаге это проще
, чтобы написать его, трудно написать его здесь.

Так что это должно быть ваше строгое доказательство для случая N.

Answer 2

OK. Скажем, у нас есть:

< P1 = P2 = < ... < = Pn, и S1 < = S2 = < ... < = Sn.

Предположим, что это утверждение неверно, и есть еще одно оптимальное решение. Это означает, что P1 сопряжен с Sk, где k> 1 в этом решении.

Теперь давайте посмотрим на что Pj, который работает в паре с S1 (если вы рисуете
его в качестве графа, эти две линии P1-Sk и Pj-S1 будет пересекаться друг с другом).

Так что меня интересуют первые две линии, которые пересекают друг друга.

Теперь подумайте, что произойдет, если мы возьмем ту же конфигурацию, но мы изменим ее на 0, а затем заменим P1 на S1 и Pj со Sk. Сумма будет уменьшаться (или она может оставаться неизменной, если P1 = Pj или S1 = Sk).

Пример:

Но если она остается той же мы можем двигаться вперед в двух последовательностей.

Так получилось, что наше оптимальное решение не является оптимальным. Это противоречие, поэтому наше предположение неверно.

Примечание 1: На самом деле в моем доказательстве я бы говорить не P1, но Pm с наименьшим м, таким образом, что Pm не в паре с Sm , но с некоторой Ск, где к> т. Я сказал P1 здесь просто для простоты.

Примечание 2: Для того, чтобы доказать эту часть:
«. А теперь подумайте, что произойдет, если взять ту же самую конфигурацию, но вместо этого мы пары P1 с S1 и Pj с Sk сумма будет уменьшаться» только подумайте, что произойдет, если у вас есть 4 номера только
P1 = P2 <
S1 < = S2

Тогда вы должны соединить их: P1-S1 и P2-S2 или перекрещены, как
P1- S2 и S1-P2. Здесь нужно разработать несколько разных случаев.

1 1 (пара 1 - равные количества)
2 2 (пара 2 - также равное количество)

1 3 (разные номера)
2 2 (равные количества)

1 5 (разные числа)
-10 (разные номера)

Примечание 3: Хорошо, я думаю, что некоторые пограничные случаи и детали должны
быть выработаны :) но в основном эта идея должна работать.

Answer 3

Observe that: 
- no matter how you arrange the pairs, the sums of each set will be constant, and so will be the difference between the two sums. 
- the 'sum of differences' can only be equal or greater than the 'difference of sums' 

Так что же это делает «сумму разницы» больше "разность сумм?

This is how I would structure the proof: 
1) what you want to prove is that sorting minimizes the cases that make the 'sum of differences' greater. 
2) what can make the 'sum of differences' greater than the 'difference of sums' are the pairs where the size relation is opposite to the size relation of the sums. For example, if in your sample the sum of all the P grades is greater than the sum of all the S grades (sumP > sumS), any pair where p < s. 
3) Now, all you have to prove is that any non-sorted arrangement can only make things worse. 

(Forgive the absence of proper math language and depth, I have an excuse for the first though, I'm new to SO and still trying to master the editor) 

Answer 4

Вы пытаетесь найти минимальную среднюю разницу. Итак, какова средняя разница: 1/n * ((p1-s1) + (p2-s2) + ... + (pn-sn)) это 1/n * ((p1 + p2 + .. + pn) - (s1 + s2 + .. + sn)), который, похоже, не зависит от упорядочения. Хорошо, вы можете сортировать его и пар, и он будет иметь минимальное среднее расстояние, а также любой другой порядок.