题目：从集合S中取出M对数，使得“每对数的差的平方和最大”，
做法：
Step1:从S中选最小的M个数，再从S中选最大的M个数，
记这2M个数分别为\(a_1,a_2,\cdots,a_{2m-1},a_{2m}(a_1<a_2<\cdots<a_{2m-1}<a_{2m})\)
Step2:最大值与最小值配对，次大值与次小值配对，次次大值与次次小值配对......
那么
即为所求
Proof：
Step2
先证明Step2，假设有M对数，为什么“最大值与最小值配对，次大值与次小值配对，次次大值与次次小值配对......”的做法能使“每对数
的差的平方和”最大
采用数学归纳法，先证明m=2的情况：已知\(a_1<a_2<a_3<a_4\),求证
- \((a_1-a_4)^2+(a_2-a_3)^2>(a_1-a_3)^2+(a_2-a_4)^2\)
- \((a_1-a_4)^2+(a_2-a_3)^2>(a_1-a_2)^2+(a_3-a_4)^2\)
先看命题1：
要证
只需证
就要证
即证
即证
即证
即
因为\(a_1<a_2<a_3<a_4\)
所以
所以
所以
命题2非常显然
因为\(|a_1-a_2|<|a_1-a_3|,|a_3-a_4|<|a_2-a_4|\)
所以显然有\((a_1-a_2)^2+(a_3-a_4)^2<(a_1-a_3)^2+(a_2-a_4)^2\)
故\((a_1-a_2)^2+(a_3-a_4)^2<(a_1-a_4)^2+(a_2-a_3)^2\)
推广(数学归纳法)
如何推广到M=i的情况呢，如果像这样把a排列起来
我们其实就要证明它们上下是一一对应的
假设我们已经证出M=i-1的情况，那么只要证a[i]一定和a[i+1]匹配即可
采用反证法，如果a[i]不与a[i+1]匹配，要么a[i]与a[k]连边(k<i) ，要么a[i]与ak连边
先看第一种情况，如果最优解中a[i]与a[2]连边
由于我们已经证出M=i-1时是成立的，所以有
如果我们仅关注a[2],a[i],a[i+2],a[i+1]的话，会发现按照M=2的情况，这样会更优
由于其他部分的平方和没有变，所以总的平方和也一定会更优，这与“最优解中a[i]与a[2]连边”矛盾，于是我们就证完了第一种情况
至于第二种情况，不妨令a[i]与a[2i-1]连边，同情况1，我们有
如果我们仅关注a[2],a[i],a[2i-1],a[2i-2]的话，会发现按照M=2的情况，这样会更优
然后我们重复上一步的策略，最终会得到
至于Step1，由于我们证出了，大数一定和小数匹配，所以选尽量大和尽量小的数，一定能让它们差的绝对值更大，也就让它们差的平方和更大