求解17个交点

〇〇

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).

〇〇

1# 〇〇 示意图

northwolves

设组成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

northwolves

可以求出: $a(n)="ceiling"( (1+sqrt(8n+1))/2 ) $

wiley

这个是下限, 需要再讨论一下是否取得到. 如果只是17个交点, 可以取三条直线平行于x轴, 两条平行于y轴, 然后任两条互相相交,且不与坐标轴平行. 讨论一下普遍的情况: 从n条互不平行的直线开始, 任取两条使得平行, 可以减少一个交点; 任取三条使得平行, 可以减少三个交点; ... 但是不确定交点的个数是否可以取遍 ${(n-1)(n-2)}/2+1$ 到 ${n(n-1)}/2$

mathe

我们可以考虑将n条直线分成$h=[n/2]>={n-1}/2$对（有可能有一条多余的直线） 那么开始做一个图是的所有n条直线两两相交，没有三点共线，那么总共${n(n-1)}/2$个交点。 每次，我们改变图案，添加一组直线平行，那么应该仅仅减少一个交点。 而最后h组平行时，交点数目应该减少到${n(n-1)}/2-h<={(n-1)(n-2)}/2+1$ 当然，上面过程是不严格的，但是感觉上应该是完全没有问题的。

geslon

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线平行，一组两直线平行，即符合本题题意。

geslon

刚刚注意到，我的楼上帖子里，有两处n（n+1）/2，是笔下误，应为n（n-1）/2。