Re: [中學] 相鄰異正整數之正差最大值

[ckchi (飄)]

※ 引述《shingai (吸收正能量)》之銘言：
: 如標題，想請問如果現在有n_1, n_2, ....,n_k , k個正整數排入一個圓桌
: 若S＝sum(|n_i-n_(i+1)|,i=1,2,...,k,n_(k+1):=n_1)
: 最大值有辦法一般化嗎？
: 碰到的題目例子是1,2,3,...,19, 而S最大值簡答是寫180，排列方式就是
: 1,19,2,18,3,17,4,16,5,15,6,14,7,13,8,12,9,11,10
: 在試完1,19,2,18,3,17,4,16,5,15,6,14,7,13,8,12,9,10,11 也是讓S＝180
: 所以不具有唯一排法
: 那這樣如何說明180會是最大呢？
: 謝謝

簡單說，這個題目要做的是：

把這19個數字圍成一圈後，把每兩個相鄰的數字拿出來比大小，
比較大的數字加上去、比較小的數字減掉。

在這樣的情況下，相當於每一個數字都使用（可選擇加或減）兩次，
但所有數字中「加」和「減」都要各用19次。

在這種情況下，如果要讓結果最大，
一定要盡量把所有大的數字都用加的、小的數字都用減的，
因此底下的組合會有最大值：
　1~9減兩次、10加一次減一次、11~19加兩次
而最大值為18*10=180

(以上為silvermare板友上一篇推文想表達的)

至於wohtp板友推文中提到另一個問題：
這樣算出來的最大值，是否可能組不成合理的圓？
答案是一定組得出來。

為了確保湊出最大值，
大數一定要被加到兩次、而小數一定要被減到兩次。
由於這題是把相鄰的數字兩兩比較大小，大的加、小的減，
因此只要讓大數組和小數組的數字彼此交錯出現就可以了。

至於大數組內的數字順序，以及小數組內的數字順序，
其實一點都不重要。
因為每一個大數旁邊一定是兩個比他小的數、
而每一個小數旁邊也一定是兩個比他大的數。

例如1~7排列時：
1726354 和 1526374 是一樣的(頭尾相連)
因為不管是1 2 3中哪一個數，都一定比5 6 7中任一個數小。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 163.32.66.180
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1460374497.A.C53.html
→ ckchi       : 題外話，所以如果有奇數(2k-1)個數字，
→ ckchi       : 總共有(k-1)!*(k-1)!種排法能達到最大值；
→ ckchi       : 如果有偶數(2k)個數字，
→ ckchi       : 則有(k-1)!*k!種排法能達到最大值。
→ ckchi       :
→ ckchi       : 而如果這些數字是連續整數(或等差數列)的話：
→ ckchi       : 則奇數(2k-1)個數字排出的最大值為2*(k-1)*k，
→ ckchi       : 偶數(2k)個數字排出的最大值為2*k*k。
→ ckchi       : (等差數列則是上面的數字再乘上公差)
推 agga        : good 連有幾種都算出來