找回密码
 欢迎注册
查看: 15789|回复: 7

[转载] 求解17个交点

[复制链接]
发表于 2009-11-12 19:56:06 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
Seventeen Intersections X infinite straight lines are drawn on a plane. There are no three lines intersecting on a single point. If there is a total of 17 intersection points, what can X be at minimum? If the question was asked for 5 intersection points, then the answer would be 4 (an example drawing is given above).
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-11-12 19:56:51 | 显示全部楼层
1# 〇〇 示意图
17.jpg
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-14 18:28:49 | 显示全部楼层
设组成n个交点至少需要a(n)条直线 显然 a(1)=2 a(2)=3 a(3)=3 ... a(n)是满足条件a(n)*(a(n-)-1)/2>=n 的最小整数. 前20项依次为: 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-14 18:43:41 | 显示全部楼层
可以求出: $a(n)="ceiling"( (1+sqrt(8n+1))/2 ) $
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-15 06:13:38 | 显示全部楼层
本帖最后由 wiley 于 2009-11-15 06:15 编辑 这个是下限, 需要再讨论一下是否取得到. 如果只是17个交点, 可以取三条直线平行于x轴, 两条平行于y轴, 然后任两条互相相交,且不与坐标轴平行. 讨论一下普遍的情况: 从n条互不平行的直线开始, 任取两条使得平行, 可以减少一个交点; 任取三条使得平行, 可以减少三个交点; ... 但是不确定交点的个数是否可以取遍 ${(n-1)(n-2)}/2+1$ 到 ${n(n-1)}/2$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-16 17:14:18 | 显示全部楼层
我们可以考虑将n条直线分成$h=[n/2]>={n-1}/2$对(有可能有一条多余的直线) 那么开始做一个图是的所有n条直线两两相交,没有三点共线,那么总共${n(n-1)}/2$个交点。 每次,我们改变图案,添加一组直线平行,那么应该仅仅减少一个交点。 而最后h组平行时,交点数目应该减少到${n(n-1)}/2-h<={(n-1)(n-2)}/2+1$ 当然,上面过程是不严格的,但是感觉上应该是完全没有问题的。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-17 08:41:52 | 显示全部楼层
n条直线两两相交,共有n(n+1)/2个交点。其中每有两线平行,可减少一个交点;每有3线平行,可减少3个交点。所以可以简单证明,n条直线交点数量可以是从n(n+1)/2 一直到(n-1)(n-2)/2 之间的任意数。 比如7条直线,若两两相交,本来应该有7*6/2=21交点,可是本题要求17交点。21-17=4,少了4个交点。4=3+1,所以七条直线中有一组3线平行,一组两直线平行,即符合本题题意。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-24 23:44:04 | 显示全部楼层
刚刚注意到,我的楼上帖子里,有两处n(n+1)/2,是笔下误,应为n(n-1)/2。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-11-24 08:11 , Processed in 0.027121 second(s), 20 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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