※ 引述《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://www.ptt.cc/bbs/Math/M.1657481308.A.FFB.html
推
07/11 07:08,
1年前
, 1F
07/11 07:08, 1F
推
07/11 20:18,
1年前
, 2F
07/11 20:18, 2F
→
07/11 20:18,
1年前
, 3F
07/11 20:18, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 3 篇)：