※ 引述《DreamYeh (天使)》之銘言： : 設a1,a2,a3,a4,a5,a6,a7,a8為8個嚴格遞增的正整數 : 且集合 {|ai-aj| : 1≦ i,j ≦ 8 && i≠j} 為18個連續正整數組成的集合 : 求a7 - a2 = ? : 原題圖片支援： : https://i.imgur.com/ehmC891.jpeg : （我有求出一些數列合乎條件，但不知有否通解，如a1~an其中 : 若干項的差構成m個連續正整數集合） 感覺這個題目滿難的， 不知道有沒有窮舉之外的思路。 從題意不難得知平移整個數列不影響答案， 而唯一重要的特徵是各數之間的差值。 比方說： 1,2,5,7 (1,3,2) 而這個差值是可以倒過來寫的 1,3,6,7 (2,3,1) 又因為整個集合中最大的元素是 a_n - a_1 （末項-首項） 而既然這些差值是連續正整數的集合， 第二大的元素就必須要是 a_n - a_1 - 1 因此a_2 - a_1 或 a_n - a_n-1 這兩個差值，至少有一個要是1 既然把整個差值倒過來不影響結果， 其實我們可以不失一般性假設數列的前兩項是 1,2,.... 我在這個基礎上些微改進了 AquaCute 前一篇的程式的執行效率， 比方說我想要找在長度8，能湊出1-22的差值的數列 我可以先固定 1,2,23 這3個元素 剩下的再從3-22之間找5個數字就行 以下是我找到的不同n值能湊出最多種差值的數列，及其相鄰項的差值 （固定第一項 =1） n=3 , max=3 1,2,4 (1,2) n=4 , max=6 1,2,5,7 (1,3,2) n=5 , max=9 1,2,3,7,10 (1,1,4,3) 1,2,5,8,10 (1,3,3,2) n=6 , max=13 1,2,3,7,11,14 (1,1,4,4,3) 1,2,5,6,12,14 (1,3,1,6,2) 1,2,7,10,12,14 (1,5,3,2,2) n=7 , max=17 1,2,3,4,9,14,18 (1,1,1,5,5,4) 1,2,3,7,11,15,18 (1,1,4,4,4,3) 1,2,3,9,13,15,18 (1,1,6,4,2,3) 1,2,3,9,13,16,18 (1,1,6,4,3,2) 1,2,9,12,14,16,18 (1,7,3,2,2,2) n=8 , max=23 1,2,3,12,16,19,22,24 (1,1,9,4,3,3,2) 1,2,5,11,17,19,22,24 (1,3,6,6,2,3,2) n=9 , max=29 1,2,3,15,19,22,25,28,30 (1,1,12,4,3,3,3,2) 1,2,4,7,14,21,25,29,30 (1,2,3,7,7,4,4,1) 1,2,5,11,17,23,25,28,30 (1,3,6,6,6,2,3,2) n=10 , max=36 1,2,4,7,14,21,28,32,36,37 (1,2,3,7,7,7,4,4,1) n=11 , max=43 1,2,4,7,14,21,28,35,39,43,44 (1,2,3,7,7,7,7,4,4,1) n=11的情況我沒算到55， 不過我有確認44跟45是沒有的，應該夠了？ 再往上，比如說n=12，我需要更好的電腦或是找到比窮舉更好的演算法才行。 有些答案在一開始在紙上試著構築的時候有找到 比如說利用等差數列的想法 n=7 的情形 (1,1,1,5,5,4) 跟 (1,1,4,4,4,3) 這種形式的答案就很直觀，也很容易在腦海中想像1-17的不同差值要怎麼湊出來 (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) (1,1,4,4,4,3) 但要推廣到n=8的情形就失敗了， 只考慮以下幾種的話，可能會以為22就是能湊出的最大值 (1,1,1,1,6,6,5) (21) (1,1,1,5,5,5,4) (22) (1,1,4,4,4,4,3) (21) (1,3,3,3,3,3,2) (18) 但事實上n=8能湊出23的兩組答案都不是以上的形式 到n=9的時候這種簡單的想法又距離最佳(29)更遠了 (1,1,1,1,1,7,7,6) (25) (1,1,1,1,6,6,6,5) (27) (1,1,1,5,5,5,5,4) (27) (1,1,4,4,4,4,4,3) (25) 但從n=9、n=10、n=11的一些情形 又能發現一些有趣的線索， 答案好像還是有某種規律存在 例如n=8的一組最佳答案，在數列中插入一個較大的間隔 (1,1,9,4,3,3,2) 在n=9的時候有長得很像的 (1,1,12,4,3,3,3,2) 到了n=10的時候，雖然這組只有湊到35，但也離很近了 (1,1,15,4,3,3,3,3,2) n=11有一個長得不太一樣的，也是能湊到最佳-1 (42) (1,1,1,16,5,4,4,4,3,3) 在n=12的情況下，從前面一些答案得出的 (1,2,3,7,7,7,7,7,4,4,1) 與 (1,1,1,20,5,4,4,4,4,3,3) 都是能湊出50的可行答案 但50會是n=12的最大值嗎？ 老實說，我不知道。 我覺得應該不是。 -- 本篇文章有很多錯誤的地方…… --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.200.112.108 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1699632708.A.7AE.html