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

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]