※ 引述《tonyhawk320 (游戏人生)》之铭言： : 把数线1-2000分为两组a1,a2,...,a1000与b1,b2,...,b1000 : 其中a1>a2>...>a1000 且 b1<b2<...<b1000 : 试求: |a1-b1|+|a2-b2|+|a3-b3|+...+|a1000-b1000| 最小值 并 证明? 下证一个比较一般的结论, 由其可知原式之值必为 1000^2 = 1000000 Lemma: 将数 1, 2, ... 2n 分为两组 a_1 > a_2 > ... > a_n 及 b_1 < b_2 < ... < b_n 则无论如何分组, 式 |a_1-b_1| + |a_2-b_2| + ... + |a_n-b_n| 之值必为 n^2 证明: 使用数学归纳法 n = 1 时显然: 一定是一组 1 另一组 2, 所求式 = |2-1| = 1 = 1^2 设 n = k-1 时成立, 考虑 n = k 的任意分组 (这里移一下写 n = k 以下行文会方便些) 不失一般性可设 a_1 = 2k, 否则必有 b_k = 2k, 将 a, b 组对调编号倒序即可 考虑 b_1 之值 若 b_1 = 1, 则 |a_1-b_1| = 2k-1, 而余下的数全部减一是为 n = k-1 的一种分组 由归纳假设知余下的绝对值和为 (k-1)^2 故全部的绝对值和为 (k-1)^2 + (2k-1) = k^2 成立 若 b_1 > 1, 为行文方便令 b_1 = h 则必然有 a_(k-t+1) = t 对 1 <= t < h 成立 (这就是在说因为 b 组最小是 h, 所以 1 ~ h-1 都在 a 组, 也一定排在最後面) 而且也一定有 b_(k-t+1) > h > a_(k-t+1) (1 ~ h 都找到位置了所以剩下的一定比 h 大, 所以也比对应 a 组数大) 考虑一个相关分组, 把 b 组的 h 和 a 组的 1 对调 在排好序後可以发现, b_1 由 h 变成 1, 因此 |a_1-b_1| 多了 h-1 但最後的 h-1 个 a 都多 1 (本来是 1 ~ h-1 变成 2 ~ h 了) 所以对应的绝对值差 |a_?-b_?| 都少 1 (因为 b 大), 正好和上面多的 h-1 抵消 但这调整後的分组就是 b_1 = 1 的情形, 所以可以知道调整前的分组之和也一样是 k^2 至此证明了在 n = k 时此绝对值总和必然是 k^2, 故由数学归纳法得证 ==== 如果上面的行文有点抽象, 以下是随便代个数字进去的说明: 原本的 1~2000 的分组, 首先 2000 只会在 a_1 或 b_1000 在 b_1000 的话就对调倒过来就变成 a_1 = 2000 了, 所求绝对值和不变 所以不失一般性设 a_1 = 2000 那看 b_1, 如果 b_1 是 1, 则 |a_1-b_1| = 1999 但 a_2 ~ a_1000 及 b_2 ~ b_1000 是 2 ~ 1999 所有人减 1 所求绝对值和不变, 但这就变成 1 ~ 1998 的分组了 归纳假设表示这部份不管怎麽分, 所求和都是 999^2 所以原分组的和就是 999^2 + 1999 = 1000^2 那如果 b_1 不是 1, 例如 b_1 = 21 好了 那 1 ~ 20 只会在 a 组, 而且一定有 a_981 = 20, a_982 = 19, 到 a_1000 = 1 b_981 ~ b_1000 也一定比 21 大 这时我们把 b 组的 21 和 a 组的 1 对换然後重排 b 组只有 b_1 变成 1, 所以 |a_1-b_1| 从 1000-21 = 979 变成 1000-1 = 999 多了 20 但 a 组最後 20 个数变成了 a_981 = 21, a_982 = 20, 到 a_1000 = 2 对应的 |a_981-b_981| 从 b_981-20 变成 b_981-21, 少了 1 |a_982-b_982| 从 b_982-19 变成 b_982-20, 也少了 1 ... |a_1000-b_1000| 从 b_1000-1 变成 b_1000-2, 也少了 1 (这边的 b 都 > 21 所以一定是这方向) 一共 20 组少 1, 刚好跟上面多的 20 抵消 所以对换後的所求绝对值和跟对换前是一样的 但对换後就变成了 b_1 = 1 的情形了, 由上所述这个状况的和也是 1000^2 因此就能得到结论: 不论怎麽分组, n = 1000 的所求和一定是 1000^2 -- 有人喜欢边玩游戏边上逼； 也有人喜欢边听歌边打字。 但是，我有个请求， 选字的时候请专心好吗？ -- 改编自「古 火田 任三郎」之开场白 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 123.194.180.251 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1657481308.A.FFB.html