Question

200分悬赏一个几何问题，急切盼望高手解答！！！

定义：平面上两点P1、P2，当直线P1P2的斜率为k时，称为“P1、P2以斜率k配对”

问题：有互不相等的m个斜率值k1,k2,...,km,以及一个平面点集{Pn}(n=1,2,3...)，若要求：对于点集中的任何一个点Pi，以k1,k2,...,km中的任一个斜率，至少能在该点集中找到一个不同的点Pj与之配对。问：该点集的最小尺寸是多少（即n的最小值）？此时该点集中的点应该满足什么排布规律？并证明为什么此时的n是满足条件的最小值？

我的猜想是n的最小值为2m，并且这时2m个点组成一个“平行多(2m)边形”。

我以m=3的情况作为例子具体说明吧，见图：
设图中MN、NL、LM的斜率分别为k1,k2,k3，则点集{A,B,C,D,E,F}满足问题条件，大家只需注意图中相关点之间连线的平行关系即可明白，毋庸赘言。对于给定的三个斜率值，我能根据一定的画图规则得到六点点集，但不能给出严格的数学证明（用符号、公式），证明六点是满足条件的最小点数，不能以理服人，m>3的情形更是无法证明。这个插图就当做抛砖引玉吧，对于高手来说也许这个问题很简单，请不吝赐教！

Answer 1

任意的斜率k，存在P、Q，使得PQ所在直线斜率为k。你那个六边形的构造上来说“2m个点组成一个平行多(2m)边

Answer 2

你的问题我现在回答不了，但是我的思路可能对你有帮助。 

    从你给出的存在性点集的构造方法中可以看出，利用k1,k2,k3,构造出基本三边形，然后在任意一条边上或者其延长线上取定第一个点，然后作平行于k1,k2，k3,的直线，交基本三边形的上或其延长线上，等到一共6个点。这6个点就是满足要求的点集。 

    其实基本三边形就是你要求的点集，只不过不是普通意义下满足要求。通过三边形的每一个顶点，只有2个斜率，如果认为自身存在第三个斜率就成了，每一个点都可以和自身构造成任意斜率的直线。那么从这个角度看，m个点的最小点集就是m。如果抛开自身构造直线，不同于自身的点自然需要2m个。而且这些点都存在于三边形的延长线上，每个边上2个。一共2m。而且6边形的对边是平行的。 

    

    对于4个点的情况，可以以正8边形为例，它的所有对角线和边组成的斜率大于4个，是满足要求的。如果是一般情形的8边形，在对边相互平行的情况下，每个点天然存在2个斜率，那么另外的2个斜率就必须从它的对角线里面获得，那么就要要求至少2条对角线必须和另外2个对边平行。这样的构造好像不存在。 

    

    感觉问题的解决，需要抽象几何的概念，比如任意两点满足要求的斜率，就认为两点之间存在一条直线，反之认为两点不在一条直线上。或者利用抽象代数里面群的概念，存基本形开始，进行扩展。同时射影几何的方法可能更加直接，有帮助，不知道这个问题是否和帕普斯定理有关系，或者考虑无穷远点可能看问题更加深刻一些。利用一般线性空间中的基与相关性，不知道怎么看。

 

按照题设，我倒是找到了四个斜率的情况，如果把无穷大也当做一个斜率值的话（如图中k3）。图中{A,B,C,D,E,F,G,H}、{A,B,I,J,K,L,M,N}、{A,B,O,P,Q,R,S,T}都是满足条件的点集，似乎也是最小点集，当然他们之间的合并也是符合条件的点集，但不是最小点集。

    总体上数学水平有限，算是抛砖引玉吧。

Answer 3

请问你是那个年级的，数学系的吗？感觉你这道题没有专业水平根本就解答不了...还是去图书馆查查相关资料吧~在百度上就算有高手会这道题，三言两语也说不清楚的，可能嫌麻烦就不乐意说了，这种高难度的题求人不如求己啊！

Answer 4

{Pn}的最小尺寸是2，对点集中的任何一个点P，任意的斜率k，总存在一点Q，使得“P、Q以斜率k配对”。换句话说，任意的斜率k，存在P、Q，使得PQ所在直线斜率为k。你那个六边形的构造上来说“2m个点组成一个‘平行多(2m)边形’。”是不对的。以AD为例，可以截取其上一段使得AB不平行于DE，显然做的到。同理，其余各边也不必平行。

Answer 5

一般解是2,4,7*2的M-3次方。对于特殊的K集为2,4,7,12*2的M-4次方，更特殊的2,4,7,12,21*2的M-5次方，更特殊的前几项为乘2-N+2。
证明根踞N维平行多面体在小于N维的投影也满足在N维时各边的平行关系。
对于M维的平行多面体在2维的投影。每一个点都有M个相邻顶点。不失一般性的让这些相邻顶点与之连线的斜率为K1到KM。对于这个多面体每一个顶点的棱的斜率显然也是K1到KM。所以此多面体的顶点投影集就是一个平面点集Pn。M维平行多面体顶点数为2的M次方。
下面证明2的M次方是最小的。
数学归纳法。对于M-1的情形。设2的M-1次方个点是最小的，新加个斜率KM。对每个点给出与KM对应的点。由于KM的任意性可知加了2的M-1次方个点。总的点数是2的M次方个。
这些点里可能有重的在M=3时可以保证有一个重点。于是M=3N=7,此后由于三角形稳定性只能对特殊的K值重复。于是有一般解2,4,7*2的M-3。

Answer 6

这是一个涉及概率的数学问题，共n个点，每两个点有一个对应k，n个点就有nX（n-1）/2个k值，即
nX（n-1）/2=m，因为m，n都为整数，并且要最小，所以，可以得出n=m=3，即3X（3-1）/2=3,也就是三角形，三个点有三个k值，不论是平面立体都适用,由于三角形属于平面，但也属于立体的特殊状态，要求n最小值，所以3是正确答案
如果回答的好记得多给分哦

Answer 7

刚看到这个题目，没来得及仔细想，以后有想法我们可以再讨论。我就说一下两个结果：

一、m=3时，6个点是最少的。证明其实很简单，我们取k1=0，k2=无穷（不允许无穷就把整个图稍微旋转一小点，无所谓的）。对于每个点Pi，都存在另外一个Pj，使得PiPj是水平线（满足k2）。我们把这些水平线全都画出来。类似地，再把垂直线全都画出来（k1）。这样就得到一个格子，格子的每一行、每一列都至少要有两个点。（一个直接推论：至少有两列、两行。）

显然至少要四个点（因为至少要有两行）。我们来证明n=4不行。假设可以的话，那么一定是恰好有两行，且每行2个点。再根据每列至少有两个点，可以看出这四个点一定构成矩形。此时k3随便取个什么值，比如1，矩形的左上（或者右下）顶点都不存在能和它以k3配对的。

再证明n=5不行。如果是两行，一行3个点，另一行2个点，则无论这5个点如何摆放，都不能满足“每列至少有两个点”。如果>=3行，则总有一行少于2个点。因此5个点不行。

综上，最少需要6个点。楼主的构造是正确的（更准确的描述：根据下面的仿射变换，可假定k1=0，k2=无穷，取一个矩形使其对角线斜率为k3，若k3>0，在由这个矩形组成的3*3格子上，取右上三点、左下三点，构造容易验证成立；若k3<0，取右下三点、左上三点。）。因此m=3时，最小值是6。

二、m=4时最小值不是8。sorry，发现证错了，但下面的结果可能对你有用：
1. 可以假设k1=0，k2=无穷。这个用到仿射变换（等价于旋转、平移、反射的组合），在这个变换下直线仍然变成直线，且任意不共线的三个点可以变为任意给定的不共线三点。我们可以用一个放射变换把k1变成0，k2变成无穷。在水平竖直的格子上讨论可能容易些。在这个格子上，每行、每列至少有两个点。
2. 我们可以取一个大框（矩形），把所有8个点都框住（有一些点在边框上，其他都在里面）。可以证明：边框的相邻顶点（同一条边的顶点）不能同时为8个点中的两个。用反证法，假设右下角和左下角的都在8个点之列。那么考虑左下角的点，过它的斜率为k3、k4的直线只能从方框内部经过，所以k3、k4>0（经过仿射变换，它们不在可以人为任意给定，但仍有两个“自由度”）。然而，在考虑右下角的点，如果它是原点，则一三象限都没有点，不可能k3或者k4>0。矛盾。
3. 如果有两条横线，则必有4条竖线，这样才能有8个点。此时，8个点布满了所有2*4=8个格点。大框的每条边的顶点都8点之列，与上面矛盾。同理，不能有2条竖线。所以，横线、竖线条数都>=3。如果有3条横线、3条竖线，则总共9个格点，那8个点必为9个格点中去掉一个。可以看出总有两个点是边框的相邻顶点，矛盾。因此，横线或者竖线>=4条。又因为每行、每列至少有两个点，所以横线（或者竖线）至多有4条。故，横线或者竖线=4条。
4. 我们再来考虑斜率为k3、k4的直线。其实类似k1、k2，这些直线也可以组成格子，只不过不是方形。平面上总共有4组直线：横线、竖线、斜率为k3的线、斜率为k4的线。如果其中的两组都<=3条，我们就用放射变换把他们变成横线和竖线（原先的横线、竖线变成了斜线），根据上面的讨论可的矛盾。因此，至多有一组<=3条线。或者说，至少有3组都是4条线（每条线上2个点，总共8个点，故不会超过4条）。我们用放射变换，把其中的两组变成横线、竖线。这样一来，横线、竖线都恰好是4条。

结论：横线、竖线恰好4条，每条横线（竖线）上都恰好有两个点。再逐个情况讨论或许能给出构造或者否定证明。但我还要上班，有时间再帮你研究。