数学研发论坛

 找回密码
 欢迎注册
楼主: 0→∞

[求助] 果树问题讨论:这两个问题等价么?

  [复制链接]
发表于 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次的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-8-11 22:29:16 | 显示全部楼层
好强
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-12 09:33:42 | 显示全部楼层
今天试着将n=11的情况写成方程形式(让计算机来做),然后输入WiMaxima求解,果然可以求出合法的6条直线的解,也就是证明了11颗树可以种6行。
r11.GIF
不过将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([A_y=0,A_x=0,B_y=0,D_x=0,C_y=0,J_x=0,I_y=0,K_x=0,B_x=1,C_x=a,D_y=1,J_y=b,B_x*C_y+C_x*A_y+A_x*B_y=B_x*A_y+C_x*B_y+C_x*A_y,B_x*I_y+I_x*A_y+A_x*B_y=B_x*A_y+I_x*B_y+I_x*A_y,D_x*J_y+J_x*A_y+A_x*D_y=D_x*A_y+J_x*D_y+J_x*A_y,D_x*K_y+K_x*A_y+A_x*D_y=D_x*A_y+K_x*D_y+K_x*A_y,E_x*J_y+J_x*B_y+B_x*E_y=E_x*B_y+J_x*E_y+J_x*B_y,E_x*L_y+L_x*B_y+B_x*E_y=E_x*B_y+L_x*E_y+L_x*B_y,F_x*K_y+K_x*C_y+C_x*F_y=F_x*C_y+K_x*F_y+K_x*C_y,F_x*L_y+L_x*C_y+C_x*F_y=F_x*C_y+L_x*F_y+L_x*C_y,G_x*H_y+H_x*D_y+D_x*G_y=G_x*D_y+H_x*G_y+H_x*D_y,G_x*L_y+L_x*D_y+D_x*G_y=G_x*D_y+L_x*G_y+L_x*D_y,G_x*I_y+I_x*E_y+E_x*G_y=G_x*E_y+I_x*G_y+I_x*E_y,G_x*K_y+K_x*E_y+E_x*G_y=G_x*E_y+K_x*G_y+K_x*E_y,H_x*I_y+I_x*F_y+F_x*H_y=H_x*F_y+I_x*H_y+I_x*F_y,H_x*J_y+J_x*F_y+F_x*H_y=H_x*F_y+J_x*H_y+J_x*F_y],[A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y,E_x,E_y,F_x,F_y,G_x,G_y,H_x,H_y,I_x,I_y,J_x,J_y,K_x,K_y,L_x,L_y])


solve([A_y=0,B_x=0,H_y=0,C_x=0,I_y=0,H_x=0,J_y=0,K_x=0,A_x=1,I_x=a,B_y=1,C_y=b,H_x*I_y+I_x*A_y+A_x*H_y=H_x*A_y+I_x*H_y+I_x*A_y,H_x*J_y+J_x*A_y+A_x*H_y=H_x*A_y+J_x*H_y+J_x*A_y,C_x*H_y+H_x*B_y+B_x*C_y=C_x*B_y+H_x*C_y+H_x*B_y,C_x*K_y+K_x*B_y+B_x*C_y=C_x*B_y+K_x*C_y+K_x*B_y,D_x*I_y+I_x*B_y+B_x*D_y=D_x*B_y+I_x*D_y+I_x*B_y,D_x*L_y+L_x*B_y+B_x*D_y=D_x*B_y+L_x*D_y+L_x*B_y,E_x*J_y+J_x*C_y+C_x*E_y=E_x*C_y+J_x*E_y+J_x*C_y,E_x*L_y+L_x*C_y+C_x*E_y=E_x*C_y+L_x*E_y+L_x*C_y,F_x*J_y+J_x*D_y+D_x*F_y=F_x*D_y+J_x*F_y+J_x*D_y,F_x*K_y+K_x*D_y+D_x*F_y=F_x*D_y+K_x*F_y+K_x*D_y,G_x*I_y+I_x*E_y+E_x*G_y=G_x*E_y+I_x*G_y+I_x*E_y,G_x*K_y+K_x*E_y+E_x*G_y=G_x*E_y+K_x*G_y+K_x*E_y,G_x*H_y+H_x*F_y+F_x*G_y=G_x*F_y+H_x*G_y+H_x*F_y,G_x*L_y+L_x*F_y+F_x*G_y=G_x*F_y+L_x*G_y+L_x*F_y],[A_x,A_y,B_x,B_y,C_x,C_y,D_x,D_y,E_x,E_y,F_x,F_y,G_x,G_y,H_x,H_y,I_x,I_y,J_x,J_y,K_x,K_y,L_x,L_y])

不过我发现mathworld上现在已经算出n=12时结果为7颗树了,也就是说可以解上面的方程了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-12 10:38:11 | 显示全部楼层
算法尚需改进呀,手工排11棵树6行,12棵树7行还都是很容易的啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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 | 显示全部楼层
刚搜索的结果
常见的独立的数学计算库并没有符号计算的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-13 12:20:58 | 显示全部楼层
而10条直线的情况我还是采用原先算法,用Wimaxima计算,总共4种情况,一种无解,另外三种的解都不是我们所需要的(但是我有点担心另外三种解我理解错误,所以可能还需要手工验算一下)。当然最好能够把上面计算过程用计算机来表示,那应该解决n=13的情况问题不大。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-8-13 12:58:00 | 显示全部楼层
能解释下式子的含义么
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-10-27 08:14 , Processed in 0.058783 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表