※ 引述《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/m.aspx?n=bbs/Math/M.1657481308.A.FFB.html