寻找最低平均成绩差

Question

给定一个有n个男孩和n个女孩的班级，其中女孩获得了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） - A2 *（B1-B2）> = 0（6）

A1（B1-B2）+ A2 *（B2-B1）> = 0（7 ）

但是（5）显然是真的，因为b1-b2 < = 0和a1 < = a2（参见（0））。

这对于N = 2严格证明。

我的直觉告诉我，这应该得到某种
很容易推广为N的情况下，也许我们可以试着从这里的
感应（在看到这些（1），（2），（3）等等。）。

几何学，可以想像，在艾和Bj为点
两个平行的数字LINEX（轴A，轴B）。一个
配对配置由与段连接从A配对
点和B中定义。您的声明基本上是
表示最佳配对是其中没有两个段（Ai，Bj）彼此交叉（它们可以与
彼此重叠/在最优解决方案中/但可能彼此不交叉） 。
对不对？现在

，如果我们做同样的事情（这我做了N = 2），
任何N，你会得到这样一个问题：“是
A1（B1-BI 1）+ A2（B2- BI2）+ A3（B3-BI3）+ ... + AN *（BN-BIN）> = 0（4' ）
真”，其中I1，I2，...，IN的任何置换（1， 2，...，N），
并且考虑到A [1] = < A [1 + 1]和b [i]于< = b [I + 1]对于每个i。

现在，我们在这里做N个感应证明（4' ）。
假设（4'）对于N和对于所有K都成立，使得K < N.
对A和B增加两个数字。假设aN + 1和bN + 1。
假设它们以其各自的SORTED序列（A，B）插入位置s1（在A中）和s2（在B中）
中。假设s1 < = s2
（相反的情况是类比的）。所以现在as1 = aN + 1和bs2 = bN + 1，
但是s1和s2是它们在NEW排序序列中的实际指数。

但是，现在证明（4“）为N + 1变成的
证明它对于N = 2的问题，因为只有这些术语（从（4”））
无论我们何时做从N到步骤N + 1。

AS1 *（BS1 - BS2）+ AS2 *（BS2 - BS1）> = 0（7' ）
和正如我们看到的，这是对于N = 2真（见上述（7））。

对于其它N-1项（其保持从（4“））中，我们得到了
不等式（4”）为真，由于从感应的假设（它是
真用于N-1）。因此，根据2和N-1的真值，我们得到了N + 1的真值。
希望你明白我是怎么做到的。在纸上，它更容易
写它，很难写在这里。

所以这应该是你对N情况的严格证明。

Answer 2

好的。假设我们有：

P1 < = P2 < = ... < =光合速率， 和 S1 < = S2 < = ... < =锡。

我们假设这个陈述不是真的， 还有另一个最佳解决方案。 这意味着我们假设P1与Sk配对，其中k> 1。

现在让我们来看看这其中与S1配对点Pj（如果你画
它作为一个图，这两条线P1-SK和PJ-S1将相互交叉）。

所以我对前两行彼此交叉感兴趣。

现在想想如果我们采用相同的配置会发生什么，但我们通过将P1与S1以及Pj与Sk配对来更改 。总和将减少 （或者如果P1 = Pj或S1 = Sk，它可以保持不变）。

实施例：

但是，如果它保持不变，我们可以在两个序列向前前进。

事实证明，我们的最佳解决方案并不是最优的。 这是矛盾的，所以我们的假设是不正确的。注1：实际上，在我的证明中，我应该说的不是P1， ，而是具有最小m的Pm，因此Pm不与Sm 配对，但有一些Sk，其中k> m。 我在这里说过P1只是为了简单。

注2：为了证明这一部分：
。“现在想想，如果采取同样的配置，但 相反，我们与S1和点Pj对P1与SK的总和将减少发生的事情” 只是觉得，如果你有4个数字会发生什么只有
P1 < = P2
S1 < = S2

那么你应该将它们配对：P1-S1和P2-S2或交叉对像
P1- S2和S1-P2。这里需要解决几个不同的情况。

11（夫妇1 - 数量相等）
2 2（夫妇2 - 也相等数量）

1 3（不同的号码）
2 2（相等数量）

1 5（不同的号码）
2 10（不同的号码）

注3：OK，我觉得有些边界情况和细节应该
制定出:)但基本上这个想法应该工作。

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）），这似乎不依赖于排序。那么你可以对它进行分类和配对，它将具有最小的平均距离以及任何其他顺序。