满足每两点连线恰含第三点且无四点共线的平面点集的可能大小n的求解
满足每两点连线恰含第三点且无四点共线的平面点集的可能大小n的求解
先跟大家唠唠这个问题的由来:我当初看错了IMO 2015的第1题,把题目里的“AB=AC(指距离相等)”理解成了“A、B、C三点共线”,结果捣鼓出这么个“山寨版”问题。后来发现和原题不是一回事,但还是想搞明白这个问题能不能证明,网上搜不到现成的思路,所以来这儿请教大家。另外提前说下,我下面提到的“集合”,全都是指平面上的点集哈。
问题的严谨表述
先给两个定义:
- 平衡集$S$:对$S$里任意两个点$A$和$B$,总能在$S$里找到第三个点$C$,使得$C$在直线$AB$上;
- 无中心集$S$:对$S$里任意两个点$A$和$B$,直线$AB$上绝不会同时存在$S$里的另外两个点$C$、$D$(说白了就是绝对不能有四点共线的情况)。
我的问题是:对于哪些大于等于3的正整数$n$,存在一个大小为$n$的点集$S$,同时满足上面这两个条件?
换个更直白的说法就是:这个点集里,任意两点的连线上恰好有第三个点,而且永远不会出现四个点共线的情况。
我的猜想
我目前觉得只有$n=3$的时候成立——就是三个共线的点,但也不确定是不是真的只有这一个解。
我目前的推导进展
先定义几个方便讨论的符号:
- $L$:所有过$S$中至少两个点的直线的集合;
- $L_p$:所有过点$p \in S$的直线的集合。
首先,如果$n>3$,所有点共线肯定不行——那样就会有至少四个点在同一条直线上,直接违反了无中心集的要求。这也能直接推出$|L| \geq 3$,这个结论很简单,我就不展开证明了。
接下来我试着用$n$来表示直线集合$L$的大小,以此缩小$n$的可能范围:
- 对任意一个点$p$,$S$里还有$n-1$个其他点。根据平衡集的要求,每个过$p$的直线上都得恰好有另外两个点(不然要么存在两点连线没第三个点,要么就会出现四点共线),所以这些点是两两配对和$p$共线的,这就意味着$n-1$必须是偶数,所以$n$一定是奇数。
- 对每个点$p$,过它的直线数量$|L_p| = \frac{n-1}{2}$(因为每条直线带两个其他点)。
- 把所有点的$|L_p|$加起来,得到的总和是$n \times \frac{n-1}{2} = \frac{n(n-1)}{2}$,但这里每条直线都被重复计算了三次(毕竟每条直线上恰好有三个点,每个点都会把这条直线算一次),所以实际的直线总数$|L| = \frac{n(n-1)}{6}$。
- 这说明$n(n-1)$必须是6的倍数。结合之前得出的$n$是奇数的结论,分情况看:
- 如果$n-1$是6的倍数,那$n=6k+1$($k$是非负整数);
- 如果$n$是3的倍数,同时$n-1$是偶数(这本来就满足,因为$n$是奇数),那$n=6k+3$($k$是非负整数)。
- 这么一来,目前筛选出来的$n$的可能值就是:${3,7,9,13,15,19,21...}$
我还尝试从几何角度入手,比如限制$S$在凸区域里之类的,但都没什么进展,现在就卡在这儿了。
备注:内容来源于stack exchange,提问作者Badikadikau
相关产品推荐
相关产品推荐

