最多五点圆数目

mathe

对于条件\[\left|\begin{matrix}\cos(2a)&\cos(a)&\sin(a)&1\\
\cos(2b)&\cos(b)&\sin(b)&1\\
\cos(2c)&\cos(c)&\sin(c)&1\\
\cos(2d)&\cos(d)&\sin(d)&1\end{matrix}\right|=0\]
我们可以改写为
\(\left|\begin{matrix}\cos(2a)+ i\sin(2a)&\cos(a)&\sin(a)&1\\
\cos(2b)+ i\sin(2b)&\cos(b)&\sin(b)&1\\
\cos(2c)+ i\sin(2a)&\cos(c)&\sin(c)&1\\
\cos(2d)+ i\sin(2a)&\cos(d)&\sin(d)&1\end{matrix}\right|\)的实部为0
也就是
\(\left|\begin{matrix}\cos(2a)+ i\sin(2a)&\cos(a)&\sin(a)i&1\\
\cos(2b)+ i\sin(2b)&\cos(b)&\sin(b)i&1\\
\cos(2c)+ i\sin(2a)&\cos(c)&\sin(c)i&1\\
\cos(2d)+ i\sin(2a)&\cos(d)&\sin(d)i&1\end{matrix}\right|\)的虚部为0
即

\(\left|\begin{matrix}\exp(2a i)&\cos(a)-\sin(a)i&2\sin(a)i&1\\
\exp(2b i)&\cos(b)-\sin(b)i&2\sin(b)i&1\\
\exp(2ci)&\cos(c)-\sin(b)i&2\sin(c)i&1\\
\exp(2di)&\cos(d)-\sin(b)i&2\sin(d)i&1\end{matrix}\right|\)的虚部为0
即
\(\left|\begin{matrix}\exp(2a i)&\cos(a)-\sin(a)i&\cos(a)+\sin(a)i&1\\
\exp(2b i)&\cos(b)-\sin(b)i&\cos(b)+\sin(b)i&1\\
\exp(2ci)&\cos(c)-\sin(b)i&\cos(c)+\sin(c)i&1\\
\exp(2di)&\cos(d)-\sin(b)i&\cos(d)+\sin(d)i&1\end{matrix}\right|\)的虚部为0
由此得出
\(\left|\begin{matrix}\exp(3a i)&1&\exp(2ai)&\exp(ai)\\
\exp(3b i)&1&\exp(2bi)&\exp(bi)\\
\exp(3c i)&1&\exp(2ci)&\exp(ci)\\
\exp(3d i)&1&\exp(2di)&\exp(di)\end{matrix}\right|\exp(-(a+b+c+d)i)\)为实数
也就是
\((\exp(ai)-\exp(bi))(\exp(ai)-\exp(ci))(\exp(ai)-\exp(di))(\exp(bi)-\exp(ci))(\exp(bi)-\exp(di))(\exp(ci)-\exp(di))\exp(-(a+b+c+d)i)\)为实数。
由于
\(\arg(\exp(ai)-\exp(bi))=\frac{a+b}2\pm\frac{\pi}2\)
我们得出
\(\frac{a+b}2+\frac{a+c}2+\frac{a+d}2+\frac{b+c}2+\frac{b+d}2+\frac{c+d}2-(a+b+c+d)\)是\(\pi\)的倍数;
也就是\(a+b+c+d\)是\(2\pi\)的倍数。

mathe

根据楼上结论，那么对于$t_k=\frac{2k\pi}{n}$,选择4个角度使得对应四点共圆的条件等价于$t_{k_1}+t_{k_2}+t_{k_3}+t_{k_4}=2m\pi$,即$k_1+k_2+k_3+k_4$是n的倍数。
而对于$t_k=\frac{(2k+1)\pi}{n}$，选择4个角度使得对应四点共圆的条件等价于$t_{k_1}+t_{k_2}+t_{k_3}+t_{k_4}=2m\pi$,即$k_1+k_2+k_3+k_4+2$是n的倍数。
经过计算可以得知，对于n是奇数，选择1~n中四个不同数，和为n的倍数或除以n的余数是n-2是相同，都是$\frac{(n-1)(n-2)(n-3)}{24}$
但是如果n是4的倍数，那么选择1~n中四个不同的数，和为n的倍数的数目是$\frac{(n-4)(n^2 - 2*n + 6)}{24}$, 余数为n-2的数目是$\frac{n(n^2-6*n+14)}{24}$
如果n除以4的余数为2，那么选择1~n中四个不同的数，和为n的倍数的数目或余数为n-2的数目都是$\frac{(n-2)(n^2 - 4*n + 6)}{24}$。
现在我们可以检验的确余数为n-2的情况和A008610[n-2]是相同的

mathe

上面分析还可以产生一个比较有意思的派生结论。
给定椭圆(非退化圆），那么椭圆上面n个不同的点中可以确定四点圆的最多数目等价于找出[0,1)上不同的n个数x_i,使得其中和为整数的四个数组合最多。

mathe

我们现在看出通过在椭圆上适当选择n个点，可以找到使得四点共圆数目比较多的解，那么我们是否总是可以在椭圆上取点，得到n个点四点共圆数目最多的解呢？
上面我们已经知道椭圆参数方程形式参数为a,b,c,d四个点共圆的充分必要条件为$a+b+c+d=2\pi$, 如果我们采用归一化的参数，即改记$a=2\pi t_a,b=2\pi t_b, c=2\pi t_c, d=2\pi t_d$
那么四点共圆的充分必要条件为$t_a+t_b+t_c+t_d$为整数，其中$0<=t_a,t_b,t_c,t_d<1$.
我们现在以n=7为例子，我们已经通过3#得知7棵树最多6组四点共圆，而且只有一组模式，分别是
ABDE, BCDF, ABFG, ACEG, DEFG, BCDG.
假设存在方案使得这7棵树按上面模式分布在椭圆上，我们不妨继续用字母A,B,C,D,E,F,G代表这7棵树在椭圆上对应的归一化的参数，于是这7个字母都是[0,1)上参数。
另外我们对实数采用模1计算（也就是计算过程每个数只保留小数部分，丢弃整数部分），那么这种计算方案对+,-,*还是继续有效的，但是不能使用除法。
于是我们可以得到方程组
A+B+D+E=0 (1)
B+C+D+F=0 (2)
A+B+F+G=0 (3)
A+C+E+G=0 (4)
D+E+F+G=0 (5)
B+C+D+G=0 (6)
从(6)式减去(2)得到
-F+G=0 （7）
这个表达式表示F和G相差一个整数，也就是他们在[0,1)必然相等，也就是两个点只能在椭圆上重叠，不符合要求。
由此得出在椭圆上选择7个不同的点，无法产生6个四点圆，只能最多5个。
所以不是所有四点圆最优问题都可以在椭圆上取到。

mathe

椭圆上取8个点问题四点共圆数目最多问题，其中圆的数目不少于10个的组合方案只能是一下几种
CDGHCEFHDEFGACDFBCDEACEGBCFGADEHBDFHAFGHBEGH
ABEFABGHACEGBDFHADEHACFHBDEGBCFGCDEFCDGHEFGH
ABCDABGHACEHADFHBCEGBDFGCDEFAEFGBEFHCFGHDEGH
ABCHABDGABEFACDFACEGADEHBCFGBDFHBEGHCDGHCEFHDEFG
CDGHCEFHDEFGACEGBDFHADEHBCFGBEGHAFGHABCD
CEGHDFGHACDGBCDHBEFHACFHADEHBCFGBDEGAEFG
CDEFCFGHDEGHACDGBEFHBCDHACEHBDFGAEFGABGH
ABGHACFHADEHBCEHBDFHCDGHAEFGBCFGBDEGCDEF
ABCFABGHABDEACEGADFHBCDGBEFHCFGHCDEHDEFG
ABCHABDGABEFACDFACEGBDFHBEGHCDGHCEFHDEFG
ABCHABDFABEGACDEACFGBDEHBFGHCDGHCEFHDEFG
ABGHACEHADFHBCEGBDFGCDEFAEFGBEFHCFGHDEGH
BCDFBCEGBDEHBFGHACFGADFHAEGHCDGHCEFHDEFG
然后通过上面解方程方案，只有
ABCHABDGABEFACDFACEGBDFHBEGHCDGHCEFHDEFG
可以有合法解，对应化简后方程组
+1A-1F+1G-1H
+1B-1E-1G+1H
+1C-1E-1F+1H
+1D-1E-1F+1G
+2E+2G
+2F-2G
于是根据最后一个方程，只能F=G+1/2, 根据倒数第二个只能E=-G或E=-G+1/2
其中E=-G可以解得
A=H+1/2
B=-H
C=-H+1/2
D=-G+1/2
E=-G
F=G+1/2
(G,H任意)
而其中E=-G+1/2可以解得:
A=H+1/2
B=-H+1/2
C=-H
D=-G
E=-G+1/2
F=G+1/2
(G,H任意)
所以椭圆上取8个点，最多10组四点共圆。而平面上取8个点我们知道最多可以12组四点共圆。

mathe

椭圆上取9个点问题四点共圆数目最多问题,
9个点四点共圆数目不少于14的组合模式有644种，计算机穷举在椭圆上有解的有三种（竟然还出现了其它两种模式，但是最多还是14个圆）:
BCDGBCEFDEFGABFIABGHACDIACEHAEGIADFHBDEICFGHBCHIDGHIEFHI
+1A+3I
+1B+1G+2I
+1C-1G+4I
+1D+1G-6I
+1E+1G-2I
+1F-1G-4I
+3G-7I
+1H-5I
+12I

ADHIAEFGDEFIDEGHFGHICDFGBDFHBDGICEFHCEGIBEHIBCDEBCFIBCGH
+1A-1E-1H-3I
+1B-1E+1H-1I
+1C-1E+1H+3I
+1D+1E+6I
+2E+2I
+1F-5I
+1G-1H-4I
+2H-2I
+12I

ABFGAEGIACHIADFHBCDEBCFIBDHIBEFHBCGHDEFICDGICEFGDEGHFGHI
+1A+1E-6I
+1B-1E-12I
+1C-1E+4I
+1D-1E-8I
+2E-2I
+1F+11I
+1G+7I
+1H+3I
+20I

mathe

41#中得出椭圆$\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$上四点共圆的充要条件是写成参数形式$(a\cos(t),b\sin(t))$后四点的参数和是$2\pi$的倍数。
那么对于双曲线又是如何呢？
对于双曲线$\frac{x^2}{a^2}-\frac{y^2}{b^2)=1$,我们可以设其上点的参数形式为$(a\csc(t), b\cot(t))$, 由此我们可以得到参数为$t_1,t_2,t_3,t_4$四点共圆的充要条件为
\(\left|\begin{matrix}a^2\csc^2(t_1)+b^2\cot^2(t_1)&a\csc(t_1)&b \cot(t_1)&1\\
a^2\csc^2(t_2)+b^2\cot^2(t_2)&a\csc(t_2)&b \cot(t_2)&1\\
a^2\csc^2(t_3)+b^2\cot^2(t_3)&a\csc(t_3)&b \cot(t_3)&1\\
a^2\csc^2(t_4)+b^2\cot^2(t_4)&a\csc(t_4)&b \cot(t_4)&1\end{matrix}\right|=0\)
最后一列乘以$b^2$加到第一列，然后第一列除以$a^2+b^2$,第二列除以a,第三列除以b得到
\(\left|\begin{matrix}\csc^2(t_1)&\csc(t_1)& \cot(t_1)&1\\
\csc^2(t_2)&\csc(t_2)& \cot(t_2)&1\\
\csc^2(t_3)&\csc(t_3)& \cot(t_3)&1\\
\csc^2(t_4)&\csc(t_4)& \cot(t_4)&1\end{matrix}\right|=0\)
然后 第 j 行乘以$\sin^2(t_j)$等，得到
\(\left|\begin{matrix}1&\sin(t_1)& \sin(t_1)\cos(t_1)&\sin^2(t_1)\\
1&\sin(t_2)& \sin(t_2)\cos(t_2)&\sin^2(t_2)\\
1&\sin(t_3)& \sin(t_3)\cos(t_3)&\sin^2(t_3)\\
1&\sin(t_4)& \sin(t_4)\cos(t_4)&\sin^2(t_4)\end{matrix}\right|=0\)
所以
\(\left|\begin{matrix}1&\sin(t_1)& \sin(2t_1)&\sin^2(t_1)\\
1&\sin(t_2)& \sin(2t_2)&\sin^2(t_2)\\
1&\sin(t_3)& \sin(2t_3)&\sin^2(t_3)\\
1&\sin(t_4)& \sin(2t_4)&\sin^2(t_4)\end{matrix}\right|=0\)
于是可以进一步变化为
\(\left|\begin{matrix}1&\sin(t_1)& \sin(2t_1)&\cos(2t_1)\\
1&\sin(t_2)& \sin(2t_2)&\cos(2t_2)\\
1&\sin(t_3)& \sin(2t_3)&\cos(2t_3)\\
1&\sin(t_4)& \sin(2t_4)&\cos(2t_4)\end{matrix}\right|=0\)
于是可以进一步变化为
\(\left|\begin{matrix}1&e^{t_1 i}& \sin(2t_1)&\cos(2t_1)\\
1&e^{t_2 i}& \sin(2t_2)&\cos(2t_2)\\
1&e^{t_3 i}& \sin(2t_3)&\cos(2t_3)\\
1&e^{t_4 i}& \sin(2t_4)&\cos(2t_4)\end{matrix}\right|\)是实数

\(\left|\begin{matrix}1&e^{t_1 i}& i\sin(2t_1)&\cos(2t_1)\\
1&e^{t_2 i}& i\sin(2t_2)&\cos(2t_2)\\
1&e^{t_3 i}& i\sin(2t_3)&\cos(2t_3)\\
1&e^{t_4 i}& i\sin(2t_4)&\cos(2t_4)\end{matrix}\right|\)实部为0

\(\left|\begin{matrix}1&e^{t_1 i}& e^{2t_1 i}&e^{-2t_1 i}\\
1&e^{t_2 i}& e^{2t_2 i}&e^{-2t_2 i}\\
1&e^{t_3 i}& e^{2t_3 i}&e^{-2t_3 i}\\
1&e^{t_4 i}& e^{2t_4 i}&e^{-2t_4 i}\end{matrix}\right|\)实部为0
最后可以变化为
\(\left|\begin{matrix}e^{-2t_1 i}&e^{-t_1 i}& 1&e^{-4t_1 i}\\
e^{-2t_2 i}&e^{-t_2 i}& 1&e^{-4t_2 i}\\
e^{-2t_3 i}&e^{-t_3 i}& 1&e^{-4t_3 i}\\
e^{-2t_4 i}&e^{-t_4 i}& 1&e^{-4t_4 i}\end{matrix}\right|e^{2(t_1+t_2+t_3+t_4)i}\)实部为0
另外如果我们看多项式
\(f(x,y,z,w)=\left|\begin{matrix}1&x&x^2&x^4\\
1&y&y^2&y^4\\
1&z&z^2&z^4\\
1&w&w^2&w^4\end{matrix}\right|\)
这是一个7次无符号牛顿多项式（变元的排列顺序只影响多项式的符号，无视符号即不变）。
任意两个变元相等都会导致行列式包含重复的行而致零，可见多项式包含因子(x-y)(x-z)(x-w)(y-z)(z-w)(w-y)。
这是一个6次无符号牛顿多项式，故只剩下一个1次牛顿多项式因子，必是(x+y+z+w)。
故$f(x,y,z,w)=\pm(x-y)(x-z)(x-w)(y-z)(y-w)(z-w)(x+y+z+w)$
由此我们得出上面四点共圆的条件为
$(e^{-t_1 i}-e^{-t_2 i})(e^{-t_1 i}-e^{-t_3 i})(e^{-t_1 i}-e^{-t_4 i})(e^{-t_2 i}-e^{-t_3 i})(e^{-t_2 i}-e^{-t_4 i})(e^{-t_3 i}-e^{-t_4 i})(e^{-t_1 i}+e^{-t_2 i}+e^{-t_3 i}+e^{-t_4 i})\e^{2(t_1+t_2+t_3+t_4)i}$的实部为0
由此得到$\frac{t_1+t_2}2+\frac{t_1+t_3}2+\frac{t_1+t_4}2+\frac{t_2+t_3}2+\frac{\t_2+t_4}2+\frac{t_3+t_4}2-t_1-t_2-t_3-t_4 +\frac{\pi}2$是$\pi$的整数倍
也就是$t_1+t_2+t_3+t_4+pi$是$2\pi$的整数倍。

那么如果换成抛物线$y=kx^2$呢？
我们类似可以得出
\(\left|\begin{matrix}x_1^4&x_1^2& x_1&1\\
x_2^4&x_2^2& x_2&1\\
x_3^4&x_3^2& x_3&1\\
x_4^4&x_4^2& x_4&1\\\end{matrix}\right|\)=0
也就是在$x_1,x_2,x_3,x_4$互不相等时$x_1+x_2+x_3+x_4=0$.
所以上述标准抛物线上不同四点共圆的充要条件是四点横坐标和为0.

mathe

mathe 发表于 2022-11-11 15:39
2#分析到:

而由于10棵5条四点共线的情况下五条直线两两各自相交，任意三条直线不共点。在射影坐标系下可 ...

8#得到11棵树最多7个5点圆。
对于12棵树，同样我们可以将一个点反演为无穷远点，然后余下11棵树，最多6行4点共线。
使用配置
//print(ABCJADEKBFGKCHIKDFHJEGIJ);
//solve([+1-1*K_X+1*I_Y*K_X,+1*D_Y-1*E_Y-1*D_Y*K_X,+1*A_Y+1*D_Y-1*E_Y,+1+1*H_Y-1*I_Y,-1+1*I_X,-1+1*E_X],[D_Y,E_Y,I_Y,K_X,A_Y,H_Y,I_X,E_X]);
//print("A_x=0 B_x=0 B_y=0 C_x=0 C_y=1 D=(1,D_y,0) F=(1,0,0) G_x=1 G_y=0 H=(1,H_y,0) J=(0,1,0) K_y=0 ");
//E_X=1,I_X=1,I_Y=s,H_Y=s-1,E_Y=t,D_Y=r,A_Y=t-r,K_X=q
LIB "solve.lib";
ring r0=0,(s,t,r,q,a,b,c,d),dp;
poly pp1=1-q+s*q;
poly pp2=r-t-r*q;
list n1=0,t-r,1;
list n2=0,0,1;
list n3=0,1,1;
list n4=1,r,0;
list n5=1,t,1;
list n6=1,0,0;
list n7=1,0,1;
list n8=1,s-1,0;
list n9=1,s,1;
list n10=0,1,0;
list n11=q,0,1;
list allnodes = n1,n2,n3,n4,n5,n6,n7,n8,n9,n10,n11;

搜索额外添加3个圆的情况，可以找到方程组
si2[1]=2304d8-8768d6+6480d4-1668d2-291
si2[2]=609263c+29664d6+129680d4-524232d2-152807
si2[3]=b-10c2d+10cd+2d3-2d
si2[4]=6a+36b2-128c2-20c+1
si2[5]=4q-36a2+62a-4c-23
si2[6]=r+q-6a-2c+7
si2[7]=t+q-6a+6
si2[8]=s-q-2c+2
解得
d=1.7137118600019076801900383270692606830
c=-0.29128371259364145452198176812175556282
b=-0.19247990049156901986074556429850884674
a=0.45014884487154511629456558338169664745
q=0.30511503475008675243776639224033144510
r=-5.1867893907080989637143364281936626860
t=-3.6042219655208160546703728919501515604
s=-2.2774523904371961566061971440031796805
射影变换阵
[-0.99999999999999999999999999999999999999 -0.15255751737504337621888319612016566442 0]
[0 -0.23674418920460869471713943096332601156 0]
[-1.7165395055834463931886429634663088414 -0.19279749468745641391949632072417377676 0.71653950558344639318864296346630884139]
变换后坐标为
A=(-0.58682109252313931635234790308256703153, -0.91064987257245459884239696440328399741)
B=(0,0)
C=(-0.29128371259364145452198176812175559499, -0.45202444004749461676720778958954576248)
D=(0.29128371259364145452198176812175554191, -1.7137118600019076801900383270692609100)
E=(1.4753414076767881292710106980281042081, -2.7965800100266088286686613853986643430)
F=(0.58256742518728290904396353624351114331, 0)
G=(1,0)
H=(0.46097611503831168910777026123501679576, -0.71535915420768688544970533885365286952)
I=(1.1633847875418099490320878739734857500, -0.96124306320175537743962947899649256928)
J=(0.79128371259364145452198176812175557108, 1.2279422488782552319017820617332316432)
K=(-1.5825674251872829090439635362435137278, 0)
得到图

所以12棵树至少可以9个五点圆。

l5.2

mathe

穷举验证上面配置加4个五点圆无解，但是加三个五点圆还有一些其它解，比如
si2[1]=d8-24d6+736d4-896d2+512 (这个关于d的方程没有实数解，淘汰）
si2[2]=17216c+43d6-1136d4+30592d2-37248
si2[3]=4b+23c2d-42cd+27d3+24d
si2[4]=42a-16b2+3c2+4c+18
si2[5]=9q-5a2-6a+c+4
si2[6]=5r-9q-4a-6c-9
si2[7]=5t-6q-6a-4c-16
si2[8]=5s-3q+2a-2c-3
添加到额外圆为:
poly gg0;
list l0;
l0=1,2,4,6;
gg0=inonecv(allnodes, l0);
l0=1,2,4,9;
poly gg1;
gg1=inonecv(allnodes, l0);
l0=1,3,5,6;
poly gg2=inonecv(allnodes, l0);
l0=1,3,5,7;
poly gg3=inonecv(allnodes, l0);
l0=2,3,4,5;
poly gg4=inonecv(allnodes, l0);
l0=2,3,4,8;
poly gg5=inonecv(allnodes, l0);

l5.3

mathe

si2[1]=25d2-1
si2[2]=5c+3
si2[3]=b+10d
si2[4]=a-1
si2[5]=3q-5
si2[6]=20r-3
si2[7]=10t+1
si2[8]=5s-2
可以取$d=1/5, c=-3/5,b=-2,a=-1,q=5/3,r=3/20,t=-1/10,s=2/5$
变换阵\(S=\begin{pmatrix}-1 &-\frac52&  0\\0  &\frac52 &   0\\-\frac16& -\frac53& -\frac56\end{pmatrix}\)
查看48#各点坐标形式，变换后结果为
A=(-3/2, 3/2)
B=(0,0)
C=(1,-1)
D=(33/10, -9/10)
E=(9/10, 3/10)
F=(6, 0)
G=(1,0)
H=(3/5, -9/5)
I=(6/5, -3/5)
J=(3/2, -3/2)
K=(3/2, 0)
poly gg0;
list l0;
l0=1,2,4,6;
gg0=inonecv(allnodes, l0);
l0=1,2,4,9;
poly gg1;
gg1=inonecv(allnodes, l0);
l0=1,3,5,7;
poly gg2=inonecv(allnodes, l0);
l0=1,3,5,8;
poly gg3=inonecv(allnodes, l0);
l0=2,5,8,10;
poly gg4=inonecv(allnodes, l0);
l0=2,5,8,11;
poly gg5=inonecv(allnodes, l0);


l5.7