于“20棵树植树问题”的来源与研究方法

作者：广西大学西校园A8信箱 黎柏文  

 “20棵树植树问题”作为数学世界三大难题之一，已受到了广大数学爱好者的垂青。然而，它的出处在哪？它是怎么来的？前人又是怎样研究这样类型的问题的呢？下文也许会让你更了解它。

    一本关于组合数学的《组合几何》（上海教育出版社 单壿  1996年6月第1版）中，第一章

“Sylvester 问题” 第30、31页写到 ：

1821年，John Jackon 在一本名为《冬天傍晚的推理娱乐》的问题集中提出如下问题：

    要种九棵树，

    橫斜共十行。

    每行须三棵，

    有何佳妙方？

1867年，Sylvester 提出更一般的问题：

平面上n个点，每四点不共线，那么恰通过三个已知点的直线至多有多少条？

采用记号，即t₄=t₅=…=t_n=0时，maxt₃是多少？这个问题称为“果园问题”。

当n=3，4，5，6时，不难证maxt₃分别为1，1，2，4(图1.17(a),(b),(c) (d)) 。

                            图1.17

例16  n=7时，maxt₃=6。

证明  每一点至多引出3条3直线（恰过3个已知点的直线），因此至多有7×3条3直线，这里每条3直线被计算3次，所以不计重数，至多7×3/3=7条3直线这时每条连结直线（过任两个已知点的直线）都是3直线。但由例1，2（定理：如果平面上n全共线，那么它们中每两点所确定的直线至少有n条。）直线存在。所以不可能每条连结直线都是3直线。于是t₃≤6。图1.18表明t₃可为6。

                       图1.18

例17  n=8时，maxt₃=7。

证明  图1.19(a)、(b)表明t₃可为7。

      另一方面，每点至多引出3条3直线，因此3直线的条数t₃≤8×3/8。如果t₃=8，那么每点恰引出3条3直线。设点P₁引出的三条直线为{P₁，P₂，P₃}，{P₁，P₄，P₅}，{P₁，P₆，P₇}，则P₁P₈为G直线（恰过2个已知点的直线）。P₈引出3条3直线与P₁引出的3条3直线交得9点A₁、A₂、A₃、B₁、B₂、B₃、C₁、C₂、C₃，如图1.19(c)所示，其中P₁P₈、P₁P₃被P₁A₃、P₁C₃分开，P₁P₈、P₈A₂被P₈A₁、P₈A₃分开。Aī、Bī、Cī（1≤ī≤3）这9点中应有6个为ζ（已知点的集合）中的点，并且除已有直线外还应有2条3直线。这2条3直线只能是{A₁，B₂，C₃}与{A₃，B₂，C₁}。但这5点如果在ζ中，那么第6点无法选取（没有4直线！），所以t₃≠8。

                   图1.19

……

第36页：1868年，Sylvester 已经证明maxt₃≥n(n-3)/6 。Burr等人在1979年改进为maxt₃≥[n(n-3)/6]+1。       

……

已经证明：在n＞7且n≠13时，

          maxt₃≤[n(n-2)/6]

证明 因为t₄=0，所以连结直线（计及重数）共

     t₂+C²₃ t₃=C² _n   条（其中3-直线计算C²₃ 次）。

     由（1981年,S.Hansen 证明除了n=7与13，恒有：恰过2个已知点的直线条数g≥n/2）

得t₃=( C² _n -t₂)/3≤(C² _n -n/2)/3=n(n-2)/6,

因此原命题成立。

注   在n=13时，已经知道t₃≤24。

……

最后一章“未解决的问题”中写到：2.平面上n个中每五点不共线，求t₄，即有多少条直线过4个已知点？

    根据以上所载，我们可以看出“20棵树植树问题”是由“果园问题”衍化而来的，它可以简单表示成：t₅=t₆=…=t_n=0时，maxt₄是多少？鉴于两问题非常相似，故可借用有关“果园问题”的研究方法来（还有很多在1～42页未能全部摘录）探讨它。

    结语：由于篇幅有限，所载不全，敬请对“20棵树植树问题”有兴趣的读者能先阅读一下关于“组合几何”方面的书籍而后再去探索答案。希望大家能从基础做起，掌握相关知识，一步一个脚印，相信这样会让你更事倍功半的！