注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

数学&华容道

Mathematics & klotski

 
 
 

日志

 
 

[转]20棵树问题  

2010-02-10 17:08:01|  分类: 数学趣题 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

数学史上有个20棵树植树问题,几个世纪以来一直享誉全球,不断给人类智慧的滋养,聪明的启迪,伴随人类文明几个世纪,点缀装饰于高档工艺美术的百花丛中,美丽经久不衰、与日俱增且不断进步,不断发展,在人类文明的进程中更加芬芳娇艳,更加靓丽多采。 20棵树植树问题,源于植树,升华在数学上的图谱学中,图谱构造的智、巧、美又广泛应用于社会的方方面面。20棵树植树问题,简单地说,就是:有20棵树,若每行四棵,问怎样种植(组排),才能使行数更多?20棵树植树问题,早在十六世纪,古希腊、古罗马、古埃及等都先后完成了十六行的排列并将美丽的图谱广泛应用于高雅装饰建筑、华丽工艺美术(图1)。进入十八世纪,德国数学家高斯猜想20棵树植树问题应能达到十八行,但一直未能见其发表绘制出的十八行图谱。直到十九世纪,此猜想才被美国的娱乐数学大师山姆·劳埃德完成并绘制出了精美的十八行图谱。

大家知道,在二十世纪七十年代,两位数学爱好者巧妙地运用电子计算机成功地绘制出了精湛美丽(由三个五角星构成)的二十行植树图(据说国外有人曾以二十万美金设奖希望对此能有新的突破)。

[转]20棵树问题 - 2666666 - 2666666
  二十世纪八十年代,我国的伍毛成功地绘制出了二十一行植树图。虽然没有给出树的具体尺寸位置,但我经过仔细计算分析证明,在树间距离满足一定关系时,这种二十一行的植树方法是正确的。http://iask.sina.com.cn/b/4958581.html
  2005年,Xianzu Lin(我想应是中国人)证明了至少存在23行的植树法,并给出了在射影面上的二十三行植树图(有两个点在无穷远处,http://www.research.att.com/~njas/sequences/a006065.gif)。
  2006年,辽宁锦州开发区笔架山小学王兴君成功地绘制出了二十三行植树图(见下图1)。虽然发表文中也没有给出树的具体尺寸位置,但我经过仔细计算分析证明,在树间距离满足一定关系时,这种二十三行的植树方法是正确的(图1中横坐标乘上非零因子a, 纵坐标乘上非零因子b都是成立的)。
  最近,河北省邢台学院学生黄阳阳(昵称eyond,蔡上人)成功地绘制出了另一个漂亮的二十三行植树图(见下图2,http://bbs.emath.ac.cn/thread-1418-1-1.html )。另外,安徽省利辛县第一中学学生李金刚去年曾来信告诉我,解出了23行的20棵树植树问题(但没看到图)。
  有趣的是,下图给出的两个二十三行植树方法中,点的坐标值都可以是整数,树之间距离比和黄金分割好像没有关系。

  理论上20棵树问题的最大行数不会超过26。证明如下:
  设平面上有n个点,记ti(2≤i≤n)为恰经过其中i个点的直线数,则我们要证明的是,当n=20时,maxt4≤26。
  【引理1】对于不在一条直线的n个点,下面不等式成立:
t2≥3+t4+2t5+3t6+…
引理1的证明在这里就不一一叙述(详见单壿著的《组合几何》,上海教育出版社,1996,注:书中少了n个点不在一条直线条件,但证明中用到了这个条件)。
  【定理】当n≠4时,maxt4≤[(n+2)(n-3)/14]
证明:先分析n个点不在一条直线上的情况
连接n个点中任意两点的直线(计算重数)共C(n,2)条,其中恰经过其中i(2≤i≤n-1)个点的直线数(计算重数)为C(i,2)ti条,故
C(n,2)=C(2,2)t2+C(3,2)t3+C(4,2)t4+…      (1)
得t2=C(n,2)-3t3-6t4-…≤n(n-2)/2-6t4      (2)
又由引理1得,t2≥3+t4             (3)
由(2)(3)消去t2后整理得,t4≤(n+2)(n-3)/14   (4)
再分析n个点在一条直线上的情况
显然,当n≠4时,t4=0,满足(4)。
当n=4时,t4=1,不满足(4)。
所以,无论n个点在不在一条直线上,当n≠4时,总有
maxt4≤[(n+2)(n-3)/14]。
当n=20时,上式得出maxt4≤26。

  综合上述,20棵树问题只剩下24行、25行和26行植树法是否存在还没有解决,我的猜想是:26行植树法是不存在的,最有可能存在的是24行植树法(虽然存在的可能性很小)。最理想的结论是:20棵树问题的最大行数为23行,且不同构的植树法就只有下图中的两种。据查国内已有人通过计算机来证明这个结论(类似四色问题证明),但计算结果还没有出来。
  在20棵树问题研究中有一个现象值得关注,那就是此问题的进展大多都是由(中国)业余数学爱好者完成而非专业数学专家完成,这说明此问题适合我们一般大众进行研究。
  相信在不远的将来,这个非常有意思的数学难题一定会得到完美解决。

20棵树问题 - 2666666 - 2666666

  评论这张
 
阅读(561)| 评论(0)
推荐

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017