果树问题讨论:这两个问题等价么？

sheng_jianguo

果树问题（特别是20棵树问题）很有意思，不知近来进展如何？ 对于楼主提出的问题，从以下分析论证可得出这两个问题是不等价的。（楼上举例都没有20棵树例子） 1.　理论上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。 （待续）

sheng_jianguo

2.对于问题2，x(20)≤30，是否有x(20)=30的例子呢？ 通过简单编程，找到了x(20)=30的例子： 1 2 3 4 1 5 6 7 1 8 9 10 1 11 12 13 1 14 15 16 1 17 18 19 2 5 8 20 2 6 11 15 2 7 14 19 2 9 13 17 2 10 12 16 3 5 12 14 3 6 9 20 3 7 13 18 3 8 11 19 3 10 15 17 4 5 16 17 4 6 12 19 4 7 10 20 4 8 13 15 4 9 14 18 5 9 15 19 5 10 11 18 6 8 16 18 6 10 13 14 7 8 12 17 7 9 11 16 11 14 17 20 12 15 18 20 13 16 19 20 当1#和20#点确定的直线（12条）不变，其它18条直线开始两点不变时，共搜索到1440种x(20)=30的例子（见附件）。 p30.rar (30.07 KB, 下载次数: 1)

2009-7-1 10:05 上传

点击文件名下载附件

从上面分析得出：问题1，maxt4(20)≤26。问题2，x(20)=30。所以这两个问题是不等价的。

数学星空

对问题1:现在主要的问题是如何构造20棵树24,25,26行的具体例子了... 对于24行好像已经是极限了,很难构造....

mathe

果树问题（特别是20棵树问题）很有意思，不知近来进展如何？ 对于楼主提出的问题，从以下分析论证可得出这两个问题是不等价的。（楼上举例都没有20棵树例子） 1.　理论上20棵树问题的最大行数不会超过26。证明如下 ... sheng_jianguo 发表于 2009-7-1 09:18

引用的引理描述有问题,应该还有很多上下文.具体内容是什么呢?

sheng_jianguo

引用的引理描述有问题,应该还有很多上下文.具体内容是什么呢? mathe 发表于 2009-7-1 21:53

原文中引理就是t2≥3+t4+2t5+3t6+…对n个点的情况都成立，没有其他条件。我仔细分析认为证明很严密没有问题，只是少了n个点不在一条直线条件（证明中用到了其对偶n条直线不相交于一点）。 书不在身边，等扫描后可以传上。

数学星空

收集到上文提到的引理现上传于此,供大家更好交流研究)

mathe

内容还是不完整. 是不是这里是指不共线的n点以及所有至少经过它们中间两个点的直线?

数学星空

是的,对于不共线的n 个点,t(i)是指恰好经过i 个点的直线数目(注意不是至少i个点的直线)

mathe

t_i的定义我清楚.主要是里面包含多少直线的问题.应该是要求所有被这n个点确定的直线都要算进去,是不是?

数学星空

为了与数学爱好者更好的讨论离散几何问题,现将<组合几何>上传于此,供大家学习交流 [local]1[/local] [local]2[/local] [local]3[/local]