某道小证明题

看到pyx最近在刷hnoi题目我就有种不好的预感。
今天他又找我问了一个问题……
平面上n个点,矩形个数的上界是多少?
(据他说是他暴力过了某道数矩形的题目之后想到的问题)
我当时相都没想就觉得是
然后觉得证明很显然……
结果在人家面前逗了好久才证明出来……
最后还是个伪证。
感觉还是有点意思的。
所以特在此记录。

下面说明我的伪证。。是怎么把pyx忽悠过去的。如果你想看正经结论,请跳过以下内容……

引理1:在a,b均为正整数数时横恒成立...
证明略。
下面开始证明:
为了讨论方便……我假设不存在四个点A,B,C,D,满足它们四点共线并且xA<=xB<=xC<=xD并且(xA+xD)/2==(xB+xC)/2
(过会再证明这样不会影响结论……)
首先n个点两两连边就要有条线段。
然后每条线段都会有一个中点,所以会有个中点。
注意到可能会有线段的中点重合,我们不妨设本质不同的中点有m个。
我们记以第i个中点为线段中点的线段个数为
显然

很容易发现告诉了我们m和a[]之后,整个点集的矩形个数计算公式为

然后我们记h(a)=
记g(n,m)为对于所有 满足len(a)=m并且并且满足为自然数 的数列a 的h(a)能取得的最大值。

记f(n,m)为一个点集如果有n个点,而且有m个本质不同的中点的时候能拥有的最多的矩形个数。

显然g(n,m)>=f(n,m)

然后我们考虑证明g(n,m-1)>=g(n,m)
显然所有 满足len(a)=m-1并且并且满足为自然数 的数列
都可以由一个 满足len(a)=m并且并且满足为自然数 的数列,合并两项得到。
那么根据一开始说的引理
所以g(n,m-1)>=g(n,m)

所以对于任意m,g(n,1)>=g(n,m)>=f(n,m)
然后显然
因为g(n,1)比所有的f(n,m)大,所以f(n,m)上界是的……所以证明完毕

结果这个伪证就这样把pyx忽悠过去了。。。

相信仔细看过上面的证明的都能发现哪里有问题……
上面证明都没有错……只是最后应该是。就这一行错了。。
所以我最后得到的上界是……
结果这个太,b了是吧……比都要松。。。。(三个点就能确定一个矩形了)
放缩放过头了……囧
之所以放过头了是因为f(n,1)在很多时候都不存在这样的点集的。。中点只有一个是不太可能的。
如果我们能知道一个点集不同的中点个数的下限r(n)是什么级别的话,大概就能用这个方式证明了
总之这也催生了一个问题:一个无三点共线的点集,本质不同的中点个数下限是?

正片开始

后来我仔细思考了一下……
发现应该上界是
首先来考虑一下怎么说明n个点的上界一定是不低于的。
这个很简单,先不妨认为n是一个偶数。
我们取一个圆,然后取它的条不同的直径。
然后取每条直径的两个端点组成这个n点的点集。。
显然我们就有了个矩形了。
然后我们这样就能知道上界的渐近下界是的了。

下面考虑上界问题。

首先设n个点里面,以点i和点j为直径的圆为
这样我们得到了个圆
注意到可能会有不同点对它们的的圆是重合的,我们不妨设本质不同的圆有m个。记作Cir[]
我们记总共有对(i,j)(i<j)满足
显然
并且(因为如果有超过条线段以同一个点为中点的话,那么根据鸽笼原理就肯定存在三个点A,B,C……满足AB和AC都以i号中点为中点,也即B和C是重合的,与我们假设不符合)

为了方便,我们不妨认为a是已经排好序的数列……这个显然对结论没有影响。
也就是说我们让
我们令k为满足的i的个数。
那么
证明如下:
首先,两个圆之间最多有2个交点。
那么我们设在n个点里面,有个点在前i个圆上。
那么显然
(减去的部分是与前面圆的交点个数)
那么如果
就会有
这就矛盾了。。。

所以矩形总数S满足:

这个应该还是比较松的。。。
更紧的上界?我暂时还没有想到啥办法。

下面是一些推广问题……
以及结论?

1.在d维空间,n个点的点集能组成的平行坐标轴的2^d个顶点的超方形个数上界是
2.在d维空间,n个点的点集能组成的平行坐标轴的2^d个顶点的超矩形个数上界是
3.在平面,n个点的点集能组成的可以任意倾斜的正方形个数上界是

感觉这个小问题还是挺有趣的……

已经颓了好几天了感觉自己啥都没干……

Comments

comments powered by Disqus