→ AquaCute : 目前人類只算到n=26 方法為窮舉法 11/11 01:36
→ emptie : ！ 11/11 02:06
※ 引述《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://www.ptt.cc/bbs/Math/M.1699632708.A.7AE.html