数学研发论坛

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

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

  [复制链接]
发表于 2009-7-1 09:18:08 | 显示全部楼层
果树问题(特别是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。
   (待续)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-1 09:49:51 | 显示全部楼层
本帖最后由 sheng_jianguo 于 2009-7-1 10:05 编辑

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:27:19 | 显示全部楼层
对问题1:现在主要的问题是如何构造20棵树24,25,26行的具体例子了...
             对于24行好像已经是极限了,很难构造....
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-1 21:53:10 | 显示全部楼层
果树问题(特别是20棵树问题)很有意思,不知近来进展如何?
对于楼主提出的问题,从以下分析论证可得出这两个问题是不等价的。(楼上举例都没有20棵树例子)
1. 理论上20棵树问题的最大行数不会超过26。证明如下 ...
sheng_jianguo 发表于 2009-7-1 09:18

引用的引理描述有问题,应该还有很多上下文.具体内容是什么呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-2 08:46:41 | 显示全部楼层
引用的引理描述有问题,应该还有很多上下文.具体内容是什么呢?
mathe 发表于 2009-7-1 21:53

原文中引理就是t2≥3+t4+2t5+3t6+…对n个点的情况都成立,没有其他条件。我仔细分析认为证明很严密没有问题,只是少了n个点不在一条直线条件(证明中用到了其对偶n条直线不相交于一点)。
书不在身边,等扫描后可以传上。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-2 10:16:20 | 显示全部楼层
收集到上文提到的引理现上传于此,供大家更好交流研究)
相交几何1.jpg
相交几何2.jpg
相交几何3.jpg
相交几何4.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-2 17:32:24 | 显示全部楼层
内容还是不完整.
是不是这里是指不共线的n点以及所有至少经过它们中间两个点的直线?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-2 17:46:54 | 显示全部楼层
是的,对于不共线的n 个点,t(i)是指恰好经过i 个点的直线数目(注意不是至少i个点的直线)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-2 18:03:30 | 显示全部楼层
t_i的定义我清楚.主要是里面包含多少直线的问题.应该是要求所有被这n个点确定的直线都要算进去,是不是?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-2 18:03:37 | 显示全部楼层
为了与数学爱好者更好的讨论离散几何问题,现将<组合几何>上传于此,供大家学习交流
[local]1[/local]
[local]2[/local]
[local]3[/local]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2021-1-22 03:09 , Processed in 0.098331 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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