论坛 › 难题征解 › 果树问题讨论:这两个问题等价么？

zgg___ 发表于 2008-8-9 20:55:18

又找到一组为28的解：
{{8,10,12,14},{6,7,9,10},{10,11,17,18},{1,7,8,11},{3,8,13,18},{7,12,18,19},{2,3,7,14},{5,11,14,20},{3,4,6,11},{6,12,13,15},{2,9,11,13},{1,10,13,20},{3,10,15,19},{5,7,13,16},{8,9,19,20},{1,3,5,9},{5,14,16,19},{5,6,8,17},{3,16,17,20},{4,13,17,19},{9,14,15,17},{2,4,5,10},{2,8,15,16},{2,6,18,20},{4,7,15,20},{1,2,12,17},{4,9,12,16},{1,4,14,18}}
12个6次的，8个5次的。

0→∞ 发表于 2008-8-11 22:29:16

好强:b:

mathe 发表于 2008-8-12 09:33:42

今天试着将n=11的情况写成方程形式（让计算机来做），然后输入WiMaxima求解，果然可以求出合法的6条直线的解，也就是证明了11颗树可以种6行。

不过将n=12的情况让WiMaxima求解,9行的唯一组合情况ABCD AEFG AHIJ BEHK BFIL CEJL CGIK DFJK DGHLWiMaxima给出无解。
8行的唯一组合AEFG AHIJ BEHK BFIL CEJL CGIK DFJK DGHL也无解
6行的第一种组合ABCD AEFG BEHI CFJK DHJL GIKL有解。但是7行的两种情况计算机都说方程太复杂，中途自动推出了。
不知道是否有谁可以用其他数学软件求解一下看看？需要注意的是会产生增根（比如有些点的坐标重合）
solve(,)


solve(,)

不过我发现mathworld上现在已经算出n=12时结果为7颗树了，也就是说可以解上面的方程了

shshsh_0510 发表于 2008-8-12 10:38:11

算法尚需改进呀，手工排11棵树6行，12棵树7行还都是很容易的啊

mathe 发表于 2008-8-12 11:37:07

手工构造可能还算容易，但是证明更大的解不存在太难了。
而且刚刚发现上面方程弄错了，重新修改了一下,n=11情况还是没有问题，但是n=12的情况更加难解了。
现在主要是遇到的都是非线性方程组。还有现在主要是使用现成的软件。如果能够自己编程进行符号运算，应该可以稍微好一些，比如大部分余下变量不允许是0等条件是可以使用的，可以降低方程很多复杂度。
我还考虑过能否用disargues定理在过滤掉一些不合法的解，不过发现大部分情况不起作用，最多可以减少一些没有必要的直线方程。

无心人 发表于 2008-8-12 16:58:43

我想，使用Maple/V结合C/C++应该可以做程序
至于独立的软件包，我想不太好找吧
不过如果用SML/NJ或者haskell等语言处理
这个问题应该不用考虑符号计算的问题
但可能计算的效率不很高
但Maple/V等的结合C/C++效率也不会很高
至于C/C++自己写代码，估计太难了

无心人 发表于 2008-8-12 17:26:49

刚搜索的结果
常见的独立的数学计算库并没有符号计算的

mathe 发表于 2008-8-13 12:18:20

发现通过射影变换将结果中一条直线投影到无穷远直线（所以其他直线中可以看到四族平行直线），
然后在一族平行直线中选择一条作为横坐标，另一族平行直线中选择一条作为纵左边建立仿射坐标系，可以极大降低计算复杂度。
我手工验算n=13的情况就可以得到13条，12条，11条直线都是无解:
ABCD AEFG AHIJ AKLM BEHK BFIL BGJM CEJL CFHM CGIK DEIM DFJK DGHL
A(0,0,1)
B(1,0,0)~
C(1,0,1)
D(d,0,1)
E(0,1,0)~
F(0,1,1)
G(0,g,1)
H(1,kH,0)~
I(Ix,Iy,1)
J(Jx,Jy,1)
K(1,kK,0)~
L(Lx,Ly,1)
M(Mx,My,1)
AHIJ, kH
Iy=kH*Ix,Jy=kH*Jx
AKLM, kK
Ly=kK*Lx, My=kK*Mx
BFIL, y=1
Iy=1,Ly=1
BGJM, y=g
Jy=g, My=g
CEJL, x=1
Jx=1, Lx=1
CFHM, kH
   1=kH*(-1), My=(Mx-1)*kH
CGIK, kK
   Iy=kK*(Ix-1), g=kK*(-1)
DEIM, x=d
   Ix=d,Mx=d
DFJK, kK
   Jy-1=kK*Jx,1=kK*(-d)
DGHL, kH
   (Ly-g)=kH*Lx, g=kH*(-d)

Iy=1
Ly=1
Jx=1
Lx=1
kK=1
g=-1
Ix=2
Jy=2,Jy=-1


AEFG AHIJ AKLM BEHK BFIL BGJM CEJL CFHM CGIK DEIM DFJK DGHL
A(1,0,1)
B(0,1,1)
C(1,Cy,0)~
D(Dx,Dy,1)
E(0,0,1)
F(1,0,0)~
G(g,0,1)
H(0,1,0)~
I(Ix,Iy,1)
J(Jx,Jy,1)
K(0,k,1)
L(Lx,Ly,1)
M(1,My,0)~

AHIJ,x=1
Ix=1,Jx=1
AKLM,My
k=-My,Ly=My*(Lx-1)
BFIL,y=1
Iy=1,Ly=1
BGJM,My
Jy-1=My*Jx, -1=My*g
CEJL,Cy
Jy=Cy*Jx,Ly=Cy*Lx
CGIK,Cy
Iy=Cy*(Ix-g),k=Cy*(-g)
DEIM,My
Dy=My*Dx,Iy=My*Ix
DFJK,y=k
Dy=k,Jy=k
DGHL,x=g
Dx=g,Lx=g


Ix=1,Jx=1
Iy=1,Ly=1
My=1,k=-1
Lx=2,g=-1;g=2,矛盾

Jy-1=1, -1=g
Jy=Cy,1=Cy*2
1=Cy*(1-g),-1=Cy*(-g)
Dy=Dx
Dy=-1,Jy=-1
Dx=g,2=g



AHIJ AKLM BCHK BDIL BEJM CFJL CGIM DFHM DGJK EFIK EGHL
A(2),B(3),C(3),D(3),E(3),F(3)

CFJL~
A(Ax,Ay,1)
B(0,0,1)
C(1,0,0)~
D(0,1,1)
E(Ex,Ey,1)
F(1,Fy,0)~
G(Gx,Gy,1)
H(1,0,1)
I(0,i,1)
J(1,Jy,0)~
K(k,0,1)
L(0,1,0)~
M(Mx,My,1)

AHIJ,Jy
Ay=Jy*(Ax-1), i=Jy*(-1)
AKLM,x=k
Ax=k,Mx=k
BEJM,Jy
Ey=Jy*Ex,My=Jy*Mx
CGIM,y=i
Gy=i,My=i
DFHM,Fy
Fy=-1,My-1=-Mx
DGJK,Jy
Gy-1=Jy*Gx,-1=Jy*k
EFIK,Fy
Ey=Fy*(Ex-k), i=Fy*(-k)
EGHL,x=1
Ex=1,Gx=1

Ex=1,Gx=1
Ax=k,Mx=k
Gy=i,My=i
Fy=-1,k=i
i=1/2,Jy=1&&Jy=-1/2 矛盾

Ay=-1/2*Jy, 1/2=Jy*(-1)
Ey=Jy,1=Jy
-1/2=Jy,-1=Jy*i
Ey=-(1-i)

mathe 发表于 2008-8-13 12:20:58

而10条直线的情况我还是采用原先算法，用Wimaxima计算，总共4种情况，一种无解，另外三种的解都不是我们所需要的（但是我有点担心另外三种解我理解错误，所以可能还需要手工验算一下）。当然最好能够把上面计算过程用计算机来表示，那应该解决n=13的情况问题不大。

无心人 发表于 2008-8-13 12:58:00

能解释下式子的含义么

查看完整版本: 果树问题讨论:这两个问题等价么？