一个著名题目——等距排布问题

mathe

n=18, 46条边，候选太多了，暂时不处理
ABAJARBFBOBRCECKCLCRDGDHDIDOEFEPEQERFHFIFRGJGMGNGOHIHMHPINIQJKJLJOKLKMKPLNLQMNMPMRNQNROPOQPQ
AGALAMAPBCBHBJBQCICJCRDEDKDLDMEKEQERFGFHFIFJFPGNGOGPHIHNHQIOIRJKJPKNKOLMLNLQMOMRNONQORPQPRQR
ABAOARBLBPCECGCICODFDHDJDLEIEKENERFHFKFMFRGNGOGPGQHKHNHQIKIMIQJLJMJPJQKPLNLPLRMOMQMRNQNROPOR
ABALAQBJBMCDCECLCMDLDODQDREKEMEPERFHFJFPFQFRGIGJGKGOGRHJHNHOHQIJIKINIPKMKQLNLPLQMNMONONPORPR
ABAMAQBJBLCDCECLCMDLDODQDREKEMEPERFHFJFPFQFRGIGJGKGOGRHJHNHOHQIJIKINIPKMKQLNLPLQMNMONONPORPR
ABAMAOBLBOCDCECLCMDJDLDPDREKEMEQERFHFJFOFQFRGIGKGOGPGRHJHNHOHPIKINIOIQJKJLKMLNLQMNMPNPNQPRQR
ABAIAMBLBNCDCECLCMDJDMDQDREKELEPERFHFIFKFQFRGIGJGNGOGQHIHKHOHPINJKJMJNKLLOLQMOMPNPNROPOQPRQR
ADAEAMAPBCBJBQBRCJCNCODEDHDQEIERFGFKFLFMGMGNGOGPHIHNHPHQIOIPIRJKJLJPKLKNKQLOLRMPMQMRNONQORQR
ABAOAQBPBRCGCHCICJDKDLDODPEFEGEJEKEPFHFIFLFOGJGNGQHIHNHRIMIQJMJRKMKPKQLMLOLRMQMRNONPNQNROQPR
ABAQARBLBRCGCHCICQDFDJDKDLEIEJEKEQERFLFOFPFRGHGMGOGRHNHPHRIOIPIQJKJMJOKNKPLMLNLRMNMOMQNPNQOP
ABACANAQBCBOBRCHCPDEDIDQDREIELEMFGFJFLFQGJGMGRHKHNHOHPIJINIOJKJPKLKMKPLMLNLQMOMRNONQORPQPRQR
ABALAQBKBRCDCECFCICQDGDHDJDREFELEMEOFLFNFPGHGKGMGOHKHNHPIKIOIPIQJLJMJNJRKQLRMNMOMQNPNQOPORPR
ABAKAQBLBRCDCECFCICQDGDHDJDREFELEMEOFLFNFPGHGKGMGOHKHNHPIKIOIPIQJLJMJNJRKQLRMNMOMQNPNQOPORPR
ABACALAQBCBMBRCHCPDHDNDODPEFEIENEQFIFOFRGJGKGLGMHPHQHRIJIKIPJKJQJRKNKOLMLNLPLQMOMPMRNONQORQR
ABAMARBEBRCDCHCICLCRDEDPDQDREJEKERFGFLFMFPFQGLGMGNGOHIHMHNHPIMIOIQJKJLJNJPKLKOKQNONPNROQORPQ
ABAOARBPBQCGCJCOCQDHDIDPDREFEGEIEOEPFHFJFQFRGMGNGOHKHLHRIKIMIPJLJNJQKLKMKOKQLNLOLPMNMQMRNPNR
ABAMANBLBNCDCECLCMDEDKDODQEKEPERFGFKFNFOFPGKGNGQGRHIHJHKHLHMIJINIOIQJNJPJRLMLOLPMQMROPOQPRQR
AJAKAOAPBLBMBNBPCECJCKCNDEDLDMDOEQERFGFIFJFOFQGHGKGOGRHIHLHNHRIMINIQJKJQKRLMLRMQNONPOPPQPRQR
ABAEAMAQBEBNBRCDCLCOCQDLDPDREGEIFGFHFQFRGHGOGPHLHMHNIJIKIMINJKJLJQJRKLKOKPMNMOMQNPNROPOQPRQR
ABALARBHBMBPCFCICKCMDFDGDKDPEGEJELEPFKFOFRGNGPGRHIHJHLHMIMIOIQJLJNJQKNKQLOLRMNMRNQNROPOQORPQ
ABAOAQBPBRCGCKCOCPDHDIDJDLEFEHELEOEPFGFIFJFKGKGQGRHLHQHRIJIMIQJNJRKMKNLMLNMNMOMQNPNROPOQPRQR
AIAOAQBJBPBRCECGCOCPDFDHDQDREIEMENEOFJFKFLFQGJGKGMGPHIHLHNHRIOIRJPJQKLKMKOKRLNLOLPMNMQMRNPNQ
ABAQARBPBRCHCICPCQDFDGDJDKEJEKEPEQERFGFLFNFRGMGOGRHIHLHMHRINIOIRJKJLJMKNKOLMLNLPMOMQNONPOQPQ
ABAKAQBLBRCDCECFCGCHDIDJDQDREGEKENEPFHFLFOFPGKGMGOHLHMHNIKIMINIQJLJMJOJRKQLRMNMONPNROPOQPQPR
ALAQARBKBQBRCGCHCICQDEDFDJDREFEKEMEOFKFNFPGHGLGMGOHLHNHPIKIMINIQJLJOJPJRKQLRMNMOMRNPNROPOQPQ
ABAOARBKBPCDCECGCIDIDJDNDREGELEMERFJFKFNFPFQGLGNGQHKHLHMHOHQIJIMIQJLJPKOKPLOMPMQMRNONQNRORPR
ABAQARBKBLCDCFCGCQCRDKDODPDREHELEOEPEQFGFLFMFOGLGNGPHLHMHNHQIJIKIMIOIQJKJNJPJQKRMNMOMRNPNROP
ABAMARBEBHBPCGCJCKCLDFDGDKDPEHEJENERFLFNFPFRGKGOGRHIHJHMILIMINIQJOJQKNKQLMLPMOMRNQNROPOQORPQ
ABAOARBGBPCECFCICPDGDJDLDNDREKENEPERFIFLFMFRGHGJGOHKHNHOHQILINIQJLJMJQKLKOKPMOMPMQMRNQNRORPQ
ABAOARBGBPCECHCOCPDGDJDKDNDRELENEPERFGFIFLFMFRGIGJHKHNHOHQILINIQJKJMJQKLKOLPMOMPMQMRNQNRORPQ
ABAQARBKBLCDCKCMCNCQDKDODPDQEFELEMENERFLFOFPFRGHGKGMGOGRHKHNHPHRIJILIMIOIQJLJNJPJQMNMONPOPQR
ANAQARBOBPBRCHCICPCQDFDHDNDPEGEIEOEQFKFMFNFRGLGMGOGRHJHKHPIJILIQJKJLJNJOKMKOKQLMLNLPMPMQNROR
ABAPAQBOBRCECGCHCQDFDIDJDREMENEPEQFMFNFOFRGHGKGMGOHLHNHOIJILINIPJKJMJPKLKMKQKRLNLQLRMNOPORPQ
ABADAMBJBMBNCFCGCKCLDEDFDGDNELENEQERFGFOFQGPGRHIHJHLHOHQIJILIPIRJKJMKMKOKPLNMQMRNONPOPOQPRQR
ABALAQBKBRCDCECFCICQDGDHDJDREFEKEMEOFKFNFPGHGLGNGPHLHMHOILIMINIQJKJMJNJRKRLQMNMONPOPOQORPQPR
ABALARBQBRCJCOCPCQCRDEDKDMDODREKENEPERFGFKFLFOFPGKGLGMGNHIHJHLHMHOIJILINIPJKJQMNMOMQNPNQOPQR
n=19, 50条边候选
AHAIAJAKBCBDBLBOCDCPCRDQDSEFELEMENEOFGFJFKFOGHGIGPGQHIHRHSIMINJKJMJRKNKSLOLPLQMNMPMRNQNSOROSPQPRQSRS
AHAIAJAKBGBJBKBOCDCLCPCRDLDQDSEFEIELERESFIFLFPFQGHGOGRGSHOHPHQIMINJKJMJRKNKSLOMNMOMPMRNONQNSPQPRQSRS
AGAJAKANBIBJBKBOCICOCPCQDEDHDPDREHEQESFGFHFNFPFQGLGMGNHNHOIOIRISJKJLJRKMKSLMLOLPLRMOMQMSNRNSPQPRQSRS
AIAJAKAQBCBDBLBQCDCOCRDPDSEFEIEOEPEQFGFHFJFKGHGLGRGSHLHMHNIQIRISJKJMJRKNKSLOLPMNMOMQMRNPNQNSOPORPSRS
AGAJAKAOBHBIBPBQCDCECNCODEDPDREQESFHFIFJFKFNGLGMGNGOHIHRHSILIMJKJLJRKMKSLMLPLRMQMSNONPNQOROSPQPRQSRS
n=20, 54条边候选
AFAHAIARBJBKBPBRCGCJCKCQDEDGDNDODQEHEIEPEQFNFOFPFRGLGMGQHIHNHSIOITJKJLJSKMKTLMLNLPLSMOMPMTNONSOTPRQSQTRSRTST
AJAKAPAQBIBJBKBRCGCHCQCRDEDFDGDHDPEFEIESETFIFNFOGHGNGSHOHTILIMJKJLJSKMKTLMLNLPLSMOMPMTNONRNSOROTPQPRQRQSQTST
n=21,57条边候选
ADAKALBJBLBQBSCICJCLCRDEDGDHDQEFEHEOEUFHFKFRFSGOGPGQGSHPHTIKIMINIRJLJNJUKOKPKRLMLTMNMPMSMTNONSNUOPOUPTQSQTQURTRUTU
ADAKALBJBLBQBSCICJCLCRDEDGDQDREGEHENEUFHFIFKFTFUGHGPGTHKHSIKIMIOJLJOJUKNKPLMLTMOMPMSMTNONPNRNUOSOUPRPTQRQSQTQURSTU
AKALASBJBLBPBRCFCHCICRDGDJDLDQEHEIEKEPEQFMFPFRFSGKGNGOGQHIHSHTIMIUJLJNJTKMKQKSLOLUMOMSMUNONPNSNTOPOUPRQTQURTRUSTTU
ADAJALBCBLBMBNCDCLCOCTDIDLDQEFEJEKEPEUFJFKFSFTGIGKGPGQGSHJHMHNHPHSIOIQIRJMKNKQLRLUMNMTMUNONROROSOTPRPSPUQTQURUSTTU
ADALASBEBIBLBQCFCGCKCMDEDLDMDNELEOETFHFKFRFUGMGNGRGSHJHKHNHQIJIOIPIQJQJRJSKSKTLPLUMNMTMUNONPOPOSOTPRPUQTQURSRUSTTU
AJALASBCBDBMBNCDCLCQCTDLDRDUEFELEQERESFGFOFPFSGHGIGMGSHIHJHOHTIJIPIUJKJNKMKNKOKPLSMNMQMRNTNUOPOQOTPRPUQRQTRUSTSUTU
AKALASBCBDBMBSCDCLCQCTDLDRDUEFELENEQERFGFNFOFPGHGIGMGNHIHKHOHTIKIPIUJKJMJOJPJSKSLNMQMRMSNTNUOPOQOTPRPUQRQTRUSTSUTU
ADAKALBGBHBRBSCFCICJCSDIDJDMDREFEKELENEOFLFPFQGHGKGNGTHKHOHUIJIPITJQJUKLKMLTLUMPMQMRMSNONPNSNTOQOSOUPQPTQURSRTRUTU
ABACADAEASBHBPBRBSCGCOCQCSDEDPDQDUEOERETFGFHFIFJFSGKGLGSHMHNHSIJIKINITJLJMJUKLKOKTLQLUMNMPMUNRNTOQOTPRPUQURTSTSUTU(有解)
AJAKAOBCBDBLBMCDCKCRCTDKDSDUEFEKEOERESFGFOFPFQGHGIGLGOHIHJHPHTIJIQIUJMJNKNLMLNLRLSMNMTMUNPNQOTOUPQPRPTQSQURSRTSUTU
AHAKAQBCBDBLBMCDCKCRCTDKDSDUEFEKENERESFGFNFOFPGIGJGMGNHIHJHLHQIJIOITJPJUKNLMLQLTLUMQMRMSNTNUOPOQOROTPQPSPURSRTSUTU
ADAKALBHBLBRBSCICJCKCSDIDJDMDREFEGEHELEMFGFKFNFOGKGTGUHLHOHUIJIPIUJQJTKPKQLNLTMPMQMRMSNONQNSNTOPOSOUPQPUQTRSRTRUTU
AHAKAOBCBDBLBMCDCKCRCTDKDSDUEIENEOEPEQFGFHFIFPFTGHGIGQGUHJHMILINJLJMJPJQKNKOLMLRLSMTMUNONTNUOROSPQPRPTQSQURSRTSUTU
AIAKAQBCBDBLBMCDCKCRCUDKDSDTEFEKENERESFGFNFOFPGHGMGNGQHIHPHQHUIJILIQJLJMJOJPKNLMLTLUMRMSNTNUOPOQOSOTPRPUQTRSRUSTTU
ADARASBEBFBHBSCJCKCLCMDEDFDMDREFEPETFQFUGHGIGNGOGSHPHQHSIKILIRISJMJNJOJRKLKNKTLOLUMRMTMUNONPNTOQOUPQPRPTQRQUSTSUTU
ADAKALBGBHBKBSCICJCLCRDGDHDMDREFEIELEMESFKFNFPFSGHGOGUHQHTILIPIUJMJNJPJRKOKQKSLNLTMOMQMRNPNQNTOPOQOUPUQTRTRUSTSUTU
ADALASBIBJBKBNCECFCGCSDEDFDMDNEFEQETFRFUGHGQGRGSHLHOHPHSIJILIOITJLJPJUKMKNKOKPLMLSMNMQMRNTNUOPOQOTPRPUQRQTRUSTSUTU

mathe

n=21中只有上面标出的一种中有解，但是含有一个自由度参数，对应的解中一个图如下

对应geogebra文件如下
21.1.ggb (38.45 KB, 下载次数: 4)

2025-5-3 11:47 上传

点击文件名下载附件

mathe

上面这个图颜色没有完全画好，RT应该和RN等同色，可以看到3个同构的n=7的构图，移动旋转一定位置后，对应位置构成正三角形。
利用这种构图，可以得出\(a(3n)>=a(n)+3n\)

mathe

n=20, 只有一种构图关系
AFAHAIARBJBKBPBRCGCJCKCQDEDGDNDODQEHEIEPEQFNFOFPFRGLGMGQHIHNHSIOITJKJLJSKMKTLMLNLPLSMOMPMTNONSOTPRQSQTRSRTST
singular求出有两种不同SCC排布有解，每种各两个解，得到4个图:

看上去第一和第四种好像构图相同，只是字母排序不同，而第2，3种看上去也相同。

mathe

n=19有三种排布，每种排布同样有2*2的解
第一种AGAJAKANBIBJBKBOCICOCPCQDEDHDPDREHEQESFGFHFNFPFQGLGMGNHNHOIOIRISJKJLJRKMKSLMLOLPLRMOMQMSNRNSPQPRQSRS

第二种AHAIAJAKBCBDBLBOCDCPCRDQDSEFELEMENEOFGFJFKFOGHGIGPGQHIHRHSIMINJKJMJRKNKSLOLPLQMNMPMRNQNSOROSPQPRQSRS

第三种AGAJAKAOBHBIBPBQCDCECNCODEDPDREQESFHFIFJFKFNGLGMGNGOHIHRHSILIMJKJLJRKMKSLMLPLRMQMSNONPNQOROSPQPRQSRS

mathe

另外发现一个比较有意思的结论，a(uv)>=a(u)v+a(v)u,
比如a(8)=2a(4)+4a(2)

mathe

alld.tgz (56.01 KB, 下载次数: 7)

2025-5-4 22:44 上传

点击文件名下载附件

附件里面是6-21所有最优解的候选方程。
主要是后缀为.geo的文件
里面主要内容类似

1. api.evalCommand("w=sqrt(3)");
   
2. api.evalCommand("ShowAxes(false)");
   
3. api.evalCommand("ShowGrid(false)");
   
4. api.evalCommand("v36^2 + (v35^2 - 1)");
   
5. api.evalCommand("TBD");
   
6. api.evalCommand("v34=(0+1*w)/2");
   
7. api.evalCommand("v33=(0+1)/2");
   
8. api.evalCommand("v32=(0+2*v36^1)/1");
   
9. api.evalCommand("v31=(0+2*v35^1+1)/1");
   
10. api.evalCommand("v30=(0+1*w*v35^1-1*v36^1)/2");
    
11. api.evalCommand("v29=(0-1*v35^1-1*w*v36^1)/2");
    
12. api.evalCommand("v28=(0+4*v36^1+1*w)/2");
    
13. api.evalCommand("v27=(0+4*v35^1+1)/2");
    
14. api.evalCommand("v26=(0+1*w*v35^1-1*v36^1)/2");
    
15. api.evalCommand("v25=(0-1*v35^1-1*w*v36^1)/2");
    
16. api.evalCommand("v24=(0)/1");
    

复制代码

其中
api.evalCommand("v36^2 + (v35^2 - 1)");
api.evalCommand("TBD");
这两行需要手工修改。
比如这里前面一条说明v35和v36的平方和为1,我们可以任意设定v35为一个角度的余弦，v36为对应正弦值。然后把这部分内容贴入GeoGebra的HTML模板文件即可。
另外一个例子如

1. api.evalCommand("w=sqrt(3)");
   
2. api.evalCommand("ShowAxes(false)");
   
3. api.evalCommand("ShowGrid(false)");
   
4. api.evalCommand("-9*v32*w + (9*v32^2 + 4)");
   
5. api.evalCommand("v31=(0+7)/3");
   
6. api.evalCommand("v30=(0-1*w)/2");
   
7. api.evalCommand("v29=(0-1)/2");
   

复制代码

那么我们需要将
api.evalCommand("-9*v32*w + (9*v32^2 + 4)");
替换为v32=***, 其中***为二次方程-9*v32*w + (9*v32^2 + 4)的任意一个解，这里w是$\sqrt{3}$

mathe

为了计算所有21个点不少于57条边的图，我们知道这个图里面肯定有一条边度数不大于\(\lfloor \frac{57\times2}{21}\rfloor=5\)，
假设最小度数为d,那么删除这个点，我们可以得到一个20个点，度数为57-d,最小度数不小于d-1的图。
也就是我们只需要提前找出所有20个点，边数不小于52，而且边数加最小度数不小于56的图集S(20,52,56)。
同样推理，我们再前面一步需要找出19个点，边数不小于47，而且边数加最小度数不小于51的图S(19,47,51)。
同样推理，我们再前面一步需要找出18个点，边数不小于43，而且边数加最小度数不小于46的图S(18,43,46)。
...
上面计算过程中，最大的图是S(14,27,30),共42,173,004个图。而S(15,31,34)含19,451,223个图，S(13,24,26)含10,276,357个图。

mathe

wayne给出的文章中给出n=22时解为60或61.
如果我们需要计算n=22中60条边以上所有解，需要计算S(21,55,59), 倒退需要计算S(15,29,32)和S(14,26,28),S(13,23,25)
其中S(14,26,28)中已经包含602,494,588个图，估计S(15,29,32)会包含更多的图，达到顶峰，这个计算花费时间会太长。
但是如果我们值计算n=22中61条边以上所有解（可能会验证61条边无解），那么只需要计算到S(21,56,60), 倒推需要计算S(15,30,33), 现在估计从S(14,26,28)直接构造S(15,30,33)需要8小时左右，看看这个图的大小，如果数目同S(14,26,28)相差不是太大,那么后面就可以继续推算下去。

王守恩

mathe 发表于 2025-5-4 07:05
另外发现一个比较有意思的结论，a(uv)>=a(u)v+a(v)u,
比如a(8)=2a(4)+4a(2)

另外发现一个比较有意思的结论，a(uv)>=a(u)v+a(v)u,
比如a(8)=2a(4)+4a(2)
a(1)=0,
a(2)=1,
a(3)=3,
a(4)=5,
a(5)=7,
a(6)=9, 9=2a(3)+3a(2),
a(7)=12,
a(8)=14, 14=2a(4)+4a(2),
a(9)=18, 18=3a(3)+3a(3),
a(10)=20, 19=2a(5)+5a(2)+,
a(11)=23,
a(12)=27, 27=3a(4)+4a(3),
a(13)=30,
a(14)=33,
a(15)=37, 36=3a(5)+5a(3)+,
a(16)=41, 40=4a(4)+4a(4)+,
a(17)=43,
a(18)=46, 45=2a(9)+9a(2)=3a(6)+6a(3)+,
a(19)=50,
a(20)=54,
a(21)=57, 57=3a(7)+7a(3),
a(22)=61,
a(23)=65,
a(24)=69, 66=2a(12)+12a(2)=3a(8)+8a(3)=4a(6)+6a(4)+,
a(25)=73,
a(26)=77,
a(27)=81, 81=3a(9)+9a(3),
a(28)=85,
a(29)=89,
a(30)=93, 90=3a(10)+10a(3)+,
a(31)=97,
a(32)=101,
a(33)=105, 102=3a(11)+11a(3)+,
a(36)=118, 117=4a(9)+9a(4)+,
a(39)=132, 129=3a(13)+13a(3)+,
a(42)=145, 141=3a(14)+14a(3)+,
a(45)=160, 156=3a(15)+15a(3)+,
a(48)=174, 171=3a(16)+16a(3)+,
a(51)=189, 180=3a(17)+17a(3)+,
a(54)=204, 192=3a(18)+18a(3)+,
a(57)=219, 207=3a(19)+19a(3)+,
a(60)=234, 223=4a(15)+15a(4)+,

上面的数据——上限数据——5#——根据shshsh的结果可以找到 https://oeis.org/A186705