想了半天 想不出方法 只有一个可能的硬方向
就是设各点坐标 然后立大方程组 利用面积公式 共线面积为0 不共线不为0 然后尝试求解的个数 或者用行列式表达 可以用一些现有定理之类
或者像4色定理那样 找个可以计算机分析的方法
还不一定成 太难了
感觉这题只是锻炼空间想象能力 但是要解起来 非常困难
还是一周前的事,当时有个同学偶然问了我一道题,说是平面上有9个相同点,至少过其中三点做一条直线,问最多可做几条直线。
我当时没怎么多想,给了一个错答案,但是正是这个错误答案导致了我后来的深入研究。思路如下:既然每点至少过3个点,那么当9个点被利用最大化的时候,每条直线上有且仅有3个点,也就是最多只有三点共线而且不存在一条直线上只有两个点共线。这时我们任意取两点,那么第三点就被唯一确定,由于每条直线上三个点中取两个点的概率P0=1/3是相同的,所以直线条数
\[\text{n=}{{\text{P}}_{0}}\times \text{C}_{9}^{2}=\frac{1}{3}\times 36=12\]
然而,正确答案是10,答案的9个点的排布如下
重新检查一遍思路,大家肯定发现了漏洞,就是我们无法保证这九个点利用最大化,因此条数一定\(\le \)12。
那么正确答案是如何得到的呢,我那位同学说只是偶然说视频刷到了这题,视频作者也没说如何得到的答案。至此,这道题的解法已经成功激发了我的好奇心。
于是我对这道题进行了以下的一些研究:
大家不难注意到,刚才的思路和漏洞都是围绕“利用最大化”展开的,顺着这个思路,那如果我们能得到这九个点的实际利用率不就可以求出答案了吗?这时我们设平面上点的个数为m,最多可画直线条数为n,某条直线上点的个数为qi,过某一点的直线条数为pj,定义某一条直线上点的个数比上常数3为这条直线的点利用指数,记为\({{\eta }_{\text{i}}}\);定义过某一点的直线条数比上总直线条数为这个点的线利用率,记为\({{\omega }_{\text{j}}}\);定义所有点数为每条直线经过的点数和,记为s。
这时我们可以得到\[\begin{align} & {{\eta }_{\text{i}}}=\frac{{{q}_{i}}}{3} \\ & {{\omega }_{\text{j}}}=\frac{{{\text{p}}_{j}}}{n} \\ \end{align}\]
进而得出\[\begin{align} & \bar{\eta }=\frac{1}{n}\sum\limits_{i=1}^{n}{{{\eta }_{i}}}=\frac{1}{3n}\sum\limits_{i=1}^{n}{{{q}_{i}}} \\ & \bar{\omega }=\frac{1}{m}\sum\limits_{j=1}^{m}{{{\omega }_{j}}=}\frac{1}{nm}\sum\limits_{j=1}^{m}{{{p}_{j}}} \\ \end{align}\]
由于所有点数\[\text{s}=f(n,{{\eta }_{i}}),s=g(m,n,{{\omega }_{j}})\]
即\[\sum\limits_{i=1}^{n}{3{{\eta }_{i}}}=\sum\limits_{j=1}^{m}{n{{\omega }_{j}}}\]
\[\begin{align} & \therefore 3n\overline{\eta }=nm\overline{\omega } \\ & \therefore \overline{\eta }=\frac{m}{3}\overline{\omega } \\ \end{align}\]
很有意思,这两个均值竟然符合线性关系。代入开头此题的数据m=9,得出\[\overline{\eta }=3\overline{\omega }\]。不难发现,点利用指数越小,点的利用程度越大,且m=9时我们可以取点利用指数的最小值1(即平面内不存在4点共线),其均值也就为1。于是得出线利用率的均值为1/3\[\bar{\omega }=\frac{1}{9}\sum\limits_{j=1}^{9}{{{\omega }_{j}}=}\frac{1}{n9}\sum\limits_{j=1}^{9}{{{p}_{j}}}=\frac{1}{3}\]
即\[\sum\limits_{j=1}^{9}{{{p}_{j}}}=3n\]
这时让我们重新回顾一下题目,“有9个相同点”,我们不难得出这9个点构成的图形一定是中心对称的,8个点将1个点包裹起来,且8个点中存在间隔分布的4个点作为图形外沿的凸角顶点,这4个点的p相同,其余4点中有两点的p相同,另外两点的p相同。令这四个点对应的p分别为p2、p3、p4、p5,中间的点对应的为p1,其余4点对应的为p6~8。则p1>p2~8,p2=p3=p4=p5,p6=p7,p8=p9。若要让线利用率大,那么p就大,p的平均数\(\overline{\text{p}}\)就越大。
但是我还是不能解出所求,还请各位指点指点。
[修改于 4个月8天前 - 2024/05/02 11:32:17]
想了半天 想不出方法 只有一个可能的硬方向
就是设各点坐标 然后立大方程组 利用面积公式 共线面积为0 不共线不为0 然后尝试求解的个数 或者用行列式表达 可以用一些现有定理之类
或者像4色定理那样 找个可以计算机分析的方法
还不一定成 太难了
感觉这题只是锻炼空间想象能力 但是要解起来 非常困难
一张对着本文图片乱画的图片.jpg
‘高端解法’ 一个一个点看 看看这个点能跟谁连 (理解错误)
'遍历大法' 设坐标 k=x1−x2/y1−y2 = x1-x3/y1-y3 并且X1X2X3 Y1Y2Y3不与历史匹配成功的重复 + 一次 (废话)
新增:可能对思路有一定帮助的文章
9个点画10条直线,要求每条直线上至少3个点-CSDN博客
时段 | 个数 |
---|---|
{{f.startingTime}}点 - {{f.endTime}}点 | {{f.fileCount}} |
200字以内,仅用于支线交流,主线讨论请采用回复功能。