最多五点圆数目

mathe

对于12棵树的四点圆问题，oeis已经给出了45个圆点例子。如果有超过46个圆，那么所有树经过圆点数目之和将为46×4=184。
由于11棵树每行3棵最多16行，所以12棵树四点圆问题每棵树最多经过16个圆。
如果每棵树15个圆，只能贡献度总度树15*12=180. 所以如果有超过46个圆的方案，那么至少有不少于四棵树需要有16个圆经过。
而对于11棵树每行3棵16行的解，只有一种方案:
print(ABCADEAHIAJKBFHBGJBIKCFICGKCHJDFJDGIDHKEFKEGHEIJ);
solve([+1+1*J_X-1*J_X*J_X,+1*H_Y-1*J_X,-2+1*G_Y+1*J_X,+1*F_Y-1*J_X,-2+1*E_Y,-2+1*D_Y,+1+1*D_X-1*J_X,-1+1*F_X,-1+1*J_Y,+1+1*G_X-1*J_X,+1*E_X-1*J_X],[J_X,H_Y,G_Y,F_Y,E_Y,D_Y,D_X,F_X,J_Y,G_X,E_X]);
print("A=(1,0,0) B_x=0 B_y=0 C_x=1 C_y=0 H=(1,H_y,0) I=(0,1,0) K_x=0 K_y=1 ");

mathe

现在对于11棵树每个圆4棵的情况有了比较好的分析代码了，
运行这个程序之前，需要安装pari/gp和Singular两个软件进行符号运算。
代码中假设gp在默认运行路径,Singular运行路径被硬编码，需要根据自己实际运行环境进行修改。
代码中会调用两个gp文件，路径也被我的代码硬编码，可能需要修改。（这两个gp文件会用于判断多项式是否存在实数解）
https://github.com/emathgroup/se ... ched/files/sd11.tgz

首先主程序为
scfg.cpp,
运行时，需要在当前目录下先创建目录sd, scfg.cpp会将运行的结果产生到这个目录下。
比较有意思的是文件开头有个宏
#define FM "0"
可以将0改为其它素数（小于2^24,但是不能太小，比如32003，如果选择太小的素数，结果可能会不正确),会提高运行速度。
这个程序的运行结果在sd目录下产生了277组候选解。
比如f527519就是其中一种被保留的配置，是一个Singular代码软件，用Singular运行它，产生f527519.out
代码scfg.cpp中数组cfg[NUMCFG]给出了所有用10棵树种12行，每行3棵树的合法配置。
其中第一个成员name是由ABCD...等字母构成的序列，每三个字母代表一行树。
然后下面一行如果是RINGP("1-t-t2")，就代表运算在满足$1-t-t^2=0$的参数t扩张的域中进行计算。如果是RINGt就是在普通有理数域加一个变参t等。
再下面给出10个点的坐标，然后可选项给出了额外的对参数的一些已知淘汰条件，比如
{
"ABEAFGAHIBFHBGJCDECFICHJDFJDGIEGHEIJ",
RINGt
"list n1=0,0,1;\n"//A, J_X=t,D_X=1+t-t2
"list n2=0,1,1;\n"//B
"list n3=1+t-t2,t2,1;\n"//C
"list n4=1+t-t2,-t,1;\n"//D
"list n5=0,1,0;\n"//E
"list n6=1,0,1;\n"//F
"list n7=1,0,0;\n"//G
"list n8=1,-1,0;\n"//H
"list n9=t,-t,1;\n"//I
"list n10=t,1,1;\n",//J
"j=t;\ni=sat(si,j)[1];\nsi=std(i);\n"
"j=t+1;\ni=sat(si,j)[1];\nsi=std(i);\n"
"j=t-1;\ni=sat(si,j)[1];\nsi=std(i);\n"
},
代表有直线ABE, AFG, AHI, BFH等。其中有一个自由参数t, A点的射影坐标为(0:0:1)就是平面坐标中圆点。E点(0:1:0)是y轴方向无穷远点等。
最后给出三个条件j=t代表t不能等于0,j=t+1代表t不能等于-1等（因为这些条件都会导致n1到n10中部分点重叠).

代码的搜索方案是如果存在一个11棵树每四棵一个圆的较多圆的方案，以其中一棵树为反演中心做反演变换，把所有经过这棵树的圆反演为过三点的直线。而不经过这颗树的圆变成经过余下10点中四个点的圆。然后再对图像进行射影变换，必然能够变成cfg[..]中一种方案，但是这时那些余下圆都被变换成经过两个共轭公共虚交点的圆锥曲线，假设这两个公共虚交点为(a+bi,c+di), (a-bi,c-di)。
对于树较多的方案，除了上面第一个点，还会有第二个点同样有很多圆经过，那么所有经过第二个点的圆如果以这个点为反演中心进行变换后也会变成cfg[..]中一种，所以代码里面会搜索至少有两个点经过的圆的数目等于12时的方案。
搜索过程固定第一棵树为反演后的无穷远点。然后对于穷举第二个点为其余的10个点并且余下其它所有树的任意排列方案以及第二棵树为反演中心后得到的直线模式是cfg[..]中任何一种方案，我们就可以得出很多额外圆被投影以后的方程，其中含额外变量a,b,c,d.
需要注意这些方程中，我们要求解的变量a,b,c,d以及t等都必须是实数。然后将这些方程提交给Singular进行化简。如果判断出无解就淘汰，不然保存在文件中，如f527519.out
Singular代码在做完方程化简以后，还顺便判断了一下是否可以在不增加任何额外约束的前提下增加更多的圆，这个使用singular中reduce函数，也就是如果reduce(g,i)=0, (其中g是多项式,i是一个方程组）那么代表g=0对于方程组i是永远成立的。singular代码会将这些额外圆的顺便输出为[x,y,z,w]，其中x,y,z,w为四个点的编号。
如附件中的f527519.out
{6, 7, 8, 10}
{6, 7, 9, 10}
[6,8,9,10]
{7, 8, 9, 10}
known 23, upbound 222
其中[6,8,9,10]代表这种配置中6,8,9,10这四点总是共圆（经过第一个点的直线不会被输出)，known 23表示这种方案至少23个圆。
原先代码还试着计算是否可以有某些圆被添加使得方程组还是继续有解，比如{6,7,8,10}就代表这四个点圆可以增加后，方程组还可能有解（但是不一定实数解), 这样我们可以给出总的圆数目的上界，这里是222，但是这个判断显然不够有效，这部分代码被我删除了，在现在的scfg.cpp里面看不到。
后来发现上界判断不够有效的主要原因是方程组化并且添加新的圆的方程后，一些额外的过滤条件并没有被使用，为此，我有增加了代码
scfg2.cpp,
它会更具scfg.cpp输出到sd目录中的配置，对这些配置做重复计算（这时需要保持FM 为"0",以便在实数域进行计算，可以用gp淘汰一些没有实数解的方程）。
重复计算:
对上面额外四点共圆方程添加以后，在同样适用一些过滤条件，排除一些非法的三点共线情况，得出圆的数目的上界。
比如这时sdo/f527519.out倒数第二行结果变成了，known 23, max 23。也就是说这种配置方案有且只能有23个圆。
但是我们知道有些方程组虽然有解，但是只包含非实数解，为此添加代码filt3.cpp,
它会调用pari/gp代码对fdo中每个结果进行检查，尽量排除一些没有实数解的情况。
其输出结果在filt3.out,比如前几行为
pass f529485, m=10,n=10, known 23, max 23
pass f516489, m=9,n=11, known 30, max 69
filter f527922
pass f307969, m=4,n=4, known 32, max 32
filter f4690
表示f527922,f4690因为只有非实数解被淘汰。
另外它还给每一个解已知圆的点圆关系输出到文件result.all (运行前确保先清空这个文件），每四个字母一个圆。运行结果还有131个结果。
另外代码norm4.cpp可用用来将每个点圆关系进行标准化，运行后结果放在result.alln,排序并且淘汰重复的余下18种在result.alls

filt3.out中大部分结果known和max相同，代表所有的圆已经找出。
我们需要关注的是max>known的以及known==max>=30时的所有解。再根据等价关系，余下需要分析的解已经不多了。
另外比如
pass f307969, m=4,n=4, known 32, max 32
我们发现判断出32个圆，打开f307969.out发现
[1,2,3,7]
[1,2,3,9]
[1,2,6,8]
[1,2,7,9]
[1,3,4,8]
[1,3,7,9]
..
说明存在5点共圆1,2,3,7,9被计算5次，所以实际上最多不超过28个圆。
而
f446313同样有5点共圆
[1,2,3,4]
[1,2,3,8]
[1,2,4,8]
...
f482153同样有五点共圆
[1,2,3,8]
[1,2,3,10]
由此所有三类不同的known 32, max32的情况都有5点共圆的情况，实际上圆的数目不超过28.

而known 31, max 31的情况只有一种，对应文件f170648.out
其中也找到了5点共圆情况:
[2,5,6,7]
[2,5,6,10]
[2,5,7,10]
[2,6,7,10]


而known=30的只有四种不同的情况，分别为
pass f406648, m=6,n=6, known 30, max 30
pass f409338, m=6,n=6, known 30, max 30
pass f516489, m=9,n=11, known 30, max 69
pass f305404, m=4,n=4, known 30, max 30
我们还需要关注的有max>known的情况，实际上这个文件里面只有known 30,max 69这一种。
f516489.out：
succ 30
si[1]=c-t
si[2]=2adt+2bt2-2bt-4dt+d
si[3]=2a2t+2b2t-a2-b2-2bd-6at+2a+4t-1
si[4]=2b2dt-2abt2-a2d-b2d-2bd2+2abt+2bt2+ad-2bt
si[5]=2a3d+2ab2d+4abd2+4abt2-a2b-b3-4a2d-2b2d-4bd2-2abt-4bt2+2ab+2ad+2bt-b
[1,2,3,4]
{1, 2, 6, 8}
{1, 2, 6, 9}
{1, 2, 6, 10}
我们可以试着用singular打开文件f516489,然后添加圆1,2,6,8
> l0=1,2,6,8;
> h0=inonecv(allnodes,l0);
> i2=si,h0;
> si2=std(i2);
> si2;
> primdecGTZ(si2);
来得到一个解看看情况。后面这部分还需要进一步分析。有可能这部分还需要进行解的合法性和实数解分析。

而程序scfg3.cpp采用另外一个角度，再已经得到至少两个点都有12个圆经过的解的情况下，分析第三个经过有12个圆经过的点，发现不存在，从而证明了不存在超过30个圆点方案。而同样方法可以证明13棵树不存在46个以上的圆。

mathe

为了处理上面known 30 max 69的情况，在filt3里面加了一点五点共圆的判断，得出如下结果
pass f529485, m=10,n=10, known 23, max 23, realknown 23, realmax 23
        {1,4,9,10}
        {2,4,6,8}
        {3,4,5,7}
pass f516489, m=9,n=11, known 30, max 69, realknown 30, realmax 33
filter f527922
pass f307969, m=4,n=4, known 32, max 32, realknown 28, realmax 28
filter f4690
pass f446313, m=7,n=7, known 32, max 32, realknown 28, realmax 28
也就是对于f516489，在已经有30个圆点情况，后面能够继续添加到只有
        {1,4,9,10}
        {2,4,6,8}
        {3,4,5,7}
其它都有五点共圆问题。
直接修改文件f516489，依次添加上面四圆中的一个，比如添加最后一个圆
list l8=4,7,8,10;
poly f8=inonecv(allnodes,l8);
list l9=3,4,5,7;
poly f9=inonecv(allnodes,l9);
poly g0=ptinline(allnodes[1]);
poly g1=ptinline(allnodes[2]);
poly g2=ptinline(allnodes[3]);
poly g3=ptinline(allnodes[4]);
poly g4=ptinline(allnodes[5]);
poly g5=ptinline(allnodes[6]);
poly g6=ptinline(allnodes[7]);
poly g7=ptinline(allnodes[8]);
poly g8=ptinline(allnodes[9]);
poly g9=ptinline(allnodes[10]);
ideal i=f0,f1,f2,f3,f4,f5,f6,f7,f8,f9;
ideal si=std(i);
结果运行结果都是无解，说明实际上已经无法继续添加了，也就是这种方法也已经确认了最多30个圆。并且我们找出了四种不同的候选30圆解需要一一确认。
而新的filt3判断出30个圆的另外三组简单候选解都包含5点共圆，实际上只有26个圆。
而19#已经给出了f516489的通解形式（具有两个额外自由度）和一个特解。所以到现在这是我们找到的唯一一类30圆解。（当然还不能排除所有点都最多只有11个圆经过的30个圆解的存在『也就是一个点10个圆经过，其余都11个圆经过的特殊方案』，这里不再做讨论了。但是只要有一个点有12个圆经过，就会归到这一类中）

mathe

试着写了一个更加一般化的代码，目标是搜索8~13棵树情况下的问题，代码为
https://github.com/emathgroup/se ... hed/files/scfgd.cpp
它用到一个数据文件
https://github.com/emathgroup/se ... ched/files/data.tgz
运行完以后的结果可以再使用
https://github.com/emathgroup/se ... hed/files/filt3.cpp
进一步处理。
修改宏NN来处理不同树的数目。
data.tgz解压后会产生很多数据文件，比如13棵树问题需要用到data/ta12中的数据。
scfgd每次可以输入对应目录下一个文件名或两个文件名（全大写字母没有后缀的）作为命令行参数，代表搜索它们的组合结果。
这样就可以在不同的环境搜索不同的组合，进行并行化处理。
输出结果存放目录由宏OUTF确定。需要注意，两个不同的数据如果同时搜索，需要使用不同的输出目录，不然会相互覆盖。

mathe

8棵树我们已经知道最多有12个四点圆，但是这个不同方案最多会有多少种呢？
由于7棵树每行3棵最多6行，查看data/ta7中也可以找到唯一方案为ADEAFGBDFCDGBEGCEF。
如果某个8树四点圆方案每棵树最多有5个圆经过，那么总共组多(5*8)/2=10个圆，而12个圆根据度数计算，每棵树都需要有6个圆经过。
所以我们可以直接选择任意两个点，让以它们为反演中心得到的直线都构成方案ADEAFGBDFCDGBEGCEF即可，由此
可以在配置scfgd.cpp参数NN为8以后，运行
./scfgd ADEAFGBDFCDGBEGCEF
得到有184个不同的文件输出，每个里面都报告可以产生12个四点圆
然后采用./filt3对结果进行过滤，并且产生result.all文件，给出12个四点圆的方案会发现所有文件的方案都是等价的。所以8棵树12个四点圆只有一种方案
ring r1=0,(a,b,c,d),dp;
poly f0=0;
list n1=0,1,0;
list n2=1,0,1;
list n3=-1,1,1;
list n4=1,0,0;
list n5=1,-1,0;
list n6=0,0,1;
list n7=0,1,1;
对应方程组
si[1]=a
si[2]=c2+bd+d2-c
自由度为2
变换以后对应坐标
A(-c + 1, -1/d*c^2 + 1/d*c)
B(1,0)
C((-c + 1)/(c^2 - 2*c + (d^2 + 1)), (c^3 - 2*c^2 + (d^2 + 1)*c - d^2)/(d*c^2 - 2*d*c + (d^3 + d)))
D(-1/d^2*c^3 + 1/d^2*c^2 - c + 1, 0)
E(1, -1/d*c^2 + 1/d*c - d)
F(0,0)
G(1, 1/d*c)
H反演平面无穷远点。
对应点圆关系为ADEHAFGHBDFHCDGHBEGHCEFHABDGABEFACDFACEGBCDEBCFG

c8.ggb (31.07 KB, 下载次数: 0)

2022-11-29 21:08 上传

点击文件名下载附件

mathe

9棵树我们已经知道最多14个四点圆，计算结果表示至少有三种完全不同的方案，点圆组合如下
BCDGBCEFDEFGABFIABGHACDIACEHAEGIADFHBDEICFGHBCHIDGHIEFHI
ABFGAEGIACHIADFHBCDEBCFIBDHIBEFHBCGHDEFICDGICEFGDEGHFGHI
ADHIAEFGDEFIDEGHFGHICDFGBDFHBDGICEFHCEGIBEHIBCDEBCFIBCGH
计算结果在文件
https://github.com/emathgroup/se ... d/files/sd9.all.tar
这个tar文件解压后是6个tgz文件，分别为sd9.i.j.tgz (0<=j<=i<=2)
其中sd9.0.0.tgz, sd9.1.1.tgz, sd9.2.2.tgz中包含上面3个解。其它候选解看上去不大像能产生更好的结果，就不再一一验证了。
每个.tgz文件里面的filt3.out给出了各个候选解的摘要信息，对应real known代表已经验证的圆的数目,real max代表圆的上界，如果real max>real known,那么前面几行{..}代表了可以额外添加的圆（但是通常这些圆不能同时添加，相互会排斥，需要进一步验证）。
另外filt3.out有些行会输出unkown状态，应该是方程太复杂，pari/gp在处理是内存异常退出，对应数据本身的.out文件里面还有它的状态。
而文件result.all给出了所有状态为pass的行的点圆关系（忘了输出unknown状态的了). result.n给出了result.all所有行标准化的结果，如果它们本质等价，标准化结果会相同，result.ns给出了标准化以后还不同的电圆关系。
这三种方案对应的具体参数如下:
sol1:
si[1]=bct-adt-bt2-bt+dt+d
si[2]=act-c2t+bdt-d2t-at2-c2-d2-at+ct+c
si[3]=a2t+b2t-c2-d2-2at+2c-1  //[(a-1)^2+b^2]t-(c-1)^2-d^2=t, t={(c-1)^2+d^2}/{(a-1)^2+b^2-1}
si[4]=bc2-a2d-b2d-c2d+bd2-d3-2adt-bt2-2bc+2ad+2cd+dt+b
si[5]=a2c+b2c-ac2+c3-ad2+cd2+c2t-2bdt+d2t+at2-c2+d2-ct-a
si[6]=c2dt+d3t+2adt2+bt3+a2d+b2d+c2d+d3+2adt-2cdt+2bt2-dt2+bc-ad-2cd-2dt-b-d
si[7]=c3t+cd2t+c2t2-2bdt2+d2t2+at3+ac2+ad2-c2t+d2t+at2-ct2-ac-bd-ct-c+t+1
si[8]=2b2dt2-abt3-a3d-ab2d-c3d-cd3+2b2dt-2abt2+2adt2+2bt3-abc+3a2d+2b2d+acd+2c2d-bd2+3adt-cdt+4bt2-2dt2+ab+2bc-ad-2cd-5dt-2b-3d
si[9]=2abdt2+b2t3+a2bd+b3d+c2d2+d4+2abdt+2b2t2-2bdt2+b2c-abd-bcd-ad2-2cd2-3bdt+d2t-b2-bd+2d2
si[10]=a4d+2a2b2d+b4d+ac3d+a2d3+b2d3+acd3+c2d3+d5+2ad3t+bd2t2-2a3d-2ab2d-3ac2d+c3d-3ad3-cd3-2bd2t-d3t-2adt2-2bt3-a2b-b3-2a2d-2b2d+2acd-3c2d+bd2-d3-4adt+2cdt-4bt2+2dt2+2ab-bc+3ad+5cd+4dt+b+d
上面方程组需要先求出满足c4t2+c4t+c4-2c3t2-2c3t-2c3+2c2d2t2+2c2d2t+2c2d2+c2t3+c2t2+c2-2cd2t2-2cd2t-2cd2+2ct2+2ct+d4t2+d4t+d4+d2t3+d2t2+d2-t3-2t2-t=0的(c,d,t),然后代入上面方程组得出a,b.
ring r1=0,(a,b,c,d,t),dp;
list n1=0,0,1;
list n2=t + 1,t,t;
list n3=1,t + 1,1;
list n4=0,1,0;
list n5=1,0,0;
list n6=1,t,0;
list n7=0,1,1;
list n8=1,0,1;
DEFADGAEHBFHCDHCFGBEG
[1,2,3,7]
[1,2,4,5]
[1,3,4,6]
[1,6,7,8]
[2,3,5,6]
[2,4,7,8]
[3,5,7,8]

c9.2.ggb (28.88 KB, 下载次数: 0)

2022-12-2 17:43 上传

点击文件名下载附件

sol2:
si[1]=a2+b2+4ac-c2-d2-2cs-2a
si[2]=2ads-ds2+bc-ad-b
si[3]=2c2s+2bds+2d2s+cs2-ac-c2-bd-d2-2cs+a
si[4]=2bcs-ds2+3bc+ad-b
si[5]=2acs-cs2+3ac-c2-bd-d2-2cs-a
si[6]=bc2-4acd+c2d+bd2+d3+2cds-bc+ad
si[7]=4b2ds+4bd2s+2cds2+ds3-2abc-2b2d-34acd+8c2d+6bd2+8d3+16cds-4ds2+2ab+5bc+11ad+bs-4b
解这个方程组需要先找出2c3s2+2c3s-2c3+c2s3-c2s2-5c2s+c2+2cd2s2+2cd2s-2cd2+2cs+d2s3-d2s2-d2s+d2=0的解，然后代入上面方程组求出a,b.
list n1=s,-s,1;
list n2=s,1,1;
list n3=1,0,1;
list n4=0,1,0;
list n5=1,0,0;
list n6=0,0,1;
list n7=1,-1,0;
list n8=0,1,1;
DEGDFHCEFCGHBEHAFGABD
[1,3,5,7]
[1,3,6,8]
[1,4,5,6]
[1,4,7,8]
[2,3,4,7]
[2,5,6,7]
[3,4,5,8]

c9.3.ggb (25.35 KB, 下载次数: 0)

2022-12-2 18:43 上传

点击文件名下载附件

sol3:
si[1]=a
si[2]=c2+bd+d2-c
si[3]=bs2+bc-2bs-2ds+d
(1-c)(d^4+c(2c-1)d^2+c^2(c-1)^2)>=0, =>s,b
BEHBFGCEFDEGCGHDFHACD
list n1=-2*s + 1,s,1;
list n2=0,1,0;
list n3=1,0,1;
list n4=-1,1,1;
list n5=1,0,0;
list n6=0,0,1;
list n7=0,1,1;
list n8=1,-1,0;
[1,5,6,8]
[2,3,5,7]
[2,3,6,8]
[2,4,5,6]
[2,4,7,8]
[3,4,5,8]
[3,4,6,7]
其中第3种方程比较容易求解，只要满足不等式$(1-c)(d^4+c(2c-1)d^2+c^2(c-1)^2)>=0$的任何c,d都可以有对应实数b,s满足方程。

c9.ggb (39.27 KB, 下载次数: 1)

2022-11-30 14:58 上传

点击文件名下载附件

发现这种情况很简单，其实就是8棵树12圆情况再找两组不在原先12圆上的三点，它们确定的圆作为新交点就可以了，上面图中是直线CD(代表过CD和无穷远点的圆）和三角形EFH的外接圆确定一个额外点A

mathe

12棵树每圆4棵树的结果在文件
https://github.com/emathgroup/se ... /files/sd12.all.tar
解压后是55个.tgz文件，其中
sd12.3.3.tgz和sd12.3.5.tgz包含45个四点圆的结果，所有确认的45个四点圆的结果都是等价的。
对应的方程如下:
CGHLDEFLCFJLCEKLFHILEGILDGJLDHKLIJKLACILBDILBEJLBFKLAHJLAGKLABCDABEHABFGACEGACFHACJKADEKADFJADGHAEFIAGIJAHIKBCEFBCGJBCHKBDEGBDFHBDJKBEIKBFIJBGHICDEHCDFGCEIJCFIKDGIKDHIJEFGHEGJKFHJK
si[1]=bc-ad-bt-dt+b
si[2]=ac+c2+bd+d2-at-ct+a+t-1
si[3]=a2+b2-c2-d2+2at+2ct-2a-2t+1
si[4]=2c2d+2d3-4adt-4cdt-bt2-dt2+4ad+3bt+5dt-2b-2d
si[5]=2c3+2cd2-2c2t+4bdt+2d2t-at2-ct2-2c2-4bd-2d2+3at+5ct+t2-2a-2c-3t+2
si[6]=4b2dt+4bd2t-abt2+cdt2-bt3-dt3-4b2d+3abt+4adt+cdt+5bt2+2dt2-2ab-2ad-8bt-3dt+4b
si[7]=4abdt+4ad2t+b2t2+4bdt2+3d2t2-4abd-3b2t-8bdt-d2t+2b2+2bd
ring r1=0,(a,b,c,d,t),dp;
list n1=1,1,1;
list n2=-1/2*t + 1/2,1/2*t,1;
list n3=0,1,0;
list n4=-t,t,1;
list n5=-t + 1,t - 1,1;
list n6=0,0,1;
list n7=t,-t + 1,0;
list n8=1,0,0;
list n9=1,0,1;
list n10=0,1,1;
list n11=-t + 1,t,1;
到现在为止找到的最有解都有两个额外的自由度，有些奇怪。其中应该有特殊的背景
其中可以先找满足方程c4-2c3t+2c2d2+c2t2+c2t-c2-2cd2t-ct2+ct+d4+d2t2+d2t-d2=0的任意c,d,t，然后求对应的a,b.
试验下来，通常选择0<c<1有解，这时可以先选择一个d使得$(4*d^2 - 1)*c^4 + 2*c^3 + (8*d^4 - 6*d^2 - 1)*c^2 + 2*d^2*c + (4*d^6 - 5*d^4)<0$,然后可以求解关于t的二次方程。

c12.ggb (115.95 KB, 下载次数: 3)

2022-12-1 20:47 上传

点击文件名下载附件

mathe

10棵树每圆4棵树的结果还没有完全结束，出现了两组22个圆点解，比较有意思的是其中一组自由度为0(打破了其它最优解自由度都是2的规律)，另外一组自由度还是2.
sd10.3.3.tgz (f48) 自由度为2的解
CDEJCDGICDFHCGHJCFIJDEGHDEFIEGIJEFHJFGHIBCEHACEIACFGBDGJADFJBDHIAHIJBEFGABCDABEJABGIABFH（标准化等价类)
AFIJGHIJCDIJBEIJABCJDEGJDFHJCEHJBFGJABDHABEFACDFACGIAEHIAFGHBCDEBCHIBDGIBEGHCDGHCEFGDEFI （点圆关系）
si[1]=a2+b2+2at+2ct+2c-2t-1
si[2]=bt2+dt2+bc-ad-bt-b
si[3]=at2+ct2+ac+bd-at-t2-a-2c+t+1
si[4]=bct-adt-bc-ad-2cd+dt+d
si[5]=act+bdt-ac-2c2+bd+ct+c
si[6]=bc2-2acd-bd2+2adt+2cdt-bc+ad+2cd-2dt-d
si[7]=c2t2+d2t2+ac2+2bcd-ad2+2c2t-2bdt-2ct2-ac-2c2-bd+c
(先求c,d,t满足(c^2 - 2*c + d^2)*t^3 + (c^2 + 2*c + d^2)*t^2 + (-5*c^2 + 2*c - d^2)*t + (2*c^3 - c^2 + 2*d^2*c - d^2)=0$
然后再根据前7式求出a,b
[1,2,4,8]
[1,2,5,6]
[1,3,4,6]
[1,3,7,9]
[1,5,8,9]
[1,6,7,8]
[2,3,4,5]
[2,3,8,9]
[2,4,7,9]
[2,5,7,8]
[3,4,7,8]
[3,5,6,7]
[4,5,6,9]
list n1=-t,-t^2 + t + 1,1;
list n2=1,t,1;
list n3=0,1,1;
list n4=0,0,1;
list n5=1,0,1;
list n6=-t,t,1;
list n7=1,0,0;
list n8=1,-1,0;
list n9=0,1,0;

c10.2.ggb (26.14 KB, 下载次数: 0)

2022-12-2 20:57 上传

点击文件名下载附件

自由度为0的解
sd10.8.8.tgz (f87)
CDEICDFJCDGHCEGJCFHIDEHJDFGIEFIJEFGHGHIJBCHJBCGIACIJBDEGBDFHADEFAEGIAFHJABCDABEJABFIABGH（标准化等价类)
CGHJBGIJAHIJAFGJBDHJCEIJDEGJEFHJDFIJABCIABDFABGHACEGACFHADGIAEFIBCDGBCEHBDEIBFHICDEFDFGH (点圆关系）
si[1]=s-2
si[2]=c-3
si[3]=b+d
si[4]=a-2
si[5]=d2-1
[1,2,3,9]
[1,2,4,6]
[1,2,7,8]
[1,3,5,7]
[1,3,6,8]
[1,4,7,9]
[1,5,6,9]
[2,3,4,7]
[2,3,5,8]
[2,4,5,9]
[2,6,8,9]
[3,4,5,6]
[4,6,7,8]
list n1=-s + 1,1,1; =>(-6/5, 2/5)
list n2=0,0,1; => (0,0)
list n3=1,s - 1,0; =>(-1,-1)
list n4=1,0,1; => (1,0)
list n5=1,s,1; => (0,2)
list n6=-s + 1,s,1; => (-2,1)
list n7=0,1,0; => (2,-2)
list n8=1,0,0; => (-4,0)
list n9=0,1,1; =>(-1/2, 1/2)

mathe

对于最多四点圆问题，已经有人给了一个不错的同心正n边形构造解。 c10m.ggb (55.87 KB, 下载次数: 0)

2022-12-8 21:33 上传

点击文件名下载附件

也就是对于2n棵树的四点圆问题，可以通过将2n棵树均匀种在两个同心位似的正n边形的顶点上。
这种方案由于对称性，任意选择外正n边形上两个顶点和内正n边形上一个顶点确定的圆，通常情况会经过内正n边形的另外一个顶点，从而形成一个四点圆。
这个方案的唯一缺陷是内外里那个正n边形确定两个圆，上面都有n个点，在n比较大时比较浪费。
而计算表示，去除内外两个正n边形内接圆以外，余下所有的四点圆构成的方程组通常还有有额外的3个自由度，所以我们可以适当调整这些点的位置而保持所有这些四点圆，然后寻求一些额外的四点圆。
为此，对于2n=10和2n=12的已知最优解，在Geogbra里面对它们再进行反演变换，去除无穷远点，分别可以得到下面的结果(蓝色圆对应上面已知的四点圆，绿色或红色圆为余下的其它四点圆)





c12m.ggb (77.81 KB, 下载次数: 0)

2022-12-8 21:33 上传

点击文件名下载附件

很显然，额外圆具有明显的规律性。
也就是内外两层n个点都可以左右对称排布。同层内左右对称的四个点都可以唯一确定一个圆。
而对于这些最有结果，再任意去掉一个经过圆最少的点(对于偶数n,所有点经过的圆数目相同，可以任意去除，对于奇数n，对称轴上两个点经过圆最少)，可以得到2n-1情况的最优解。
所以现在余下的问题是，对于任意n,这种构造方案我们如何找出一组合法的坐标。另外是能否证明其最优性。
比如对于2n=14时，我试着用Singular求解，可以得出14棵树71个四点圆的方程组是有解的（同样两个自由度), 由此得出13棵树可以有53个四点圆。
但是余下方程组很复杂，我还找不出数值解。

mathe

上面2n=14时的singular代码:
https://github.com/emathgroup/se ... ttached/files/g2.sg
输出结果在
https://github.com/emathgroup/se ... hed/files/g2.sg.out
现在p和q都已经解得，但是参数a,b,c,d对应的方程有点太复杂。
比较奇怪的是2n=14时只有一个自由度而不是两个自由度。

=================================================
求得方程组一组高精度解以后发现解对应的点退化了（3个坐标都是0），所以这种情况无解而不是有解