万维百科

西尔维斯特-加莱定理

西尔维斯特–加莱定理(Sylvester–Gallai theorem)说明若在平面上有有限数目的,点的数目多于2,它们不是全部共线,有一条线上刚好有两点,如果过任意两点的直线都必过第三点,则所有的点共线。

这个定理在无限点的情况并不成立,可以考虑格点

证明

Tibor gallai2.svg

以下使用无穷递降法

  1. 在平面上有有限多点,若它们都共线,那我们就找到想要的东西;若非,定义一条“连线”为一条连起来至少有两点的线。设I为一条连线,因为不是所有点都共线,至少有一点P不属于I。
  2. 若I不是有刚好两点,I便至少有三点,称为A,B,C。不失一般性,设B在A和C之间,因为,所以两只角不可能同时是钝角。不失一般性设不是钝角,而是锐角或直角。
  3. 设连结C和P的线为m,m是不包括B的连线,而且B和m的距离比P和I的距离小。
  4. 以B和m取代第二步的P和I。这个动作不可能无穷次重复,因为若能无穷次重复,连线和某一不在连线上的点距离便会得出一个无穷递降的序列,但只有有限个点和有限条连线,这是不可能的。因此,至少有一条线刚好有两点。

推广

Dirac的猜想的反例。

这个定理说明了在所有点至少有一条线有刚好两点。在什么情况下,只有一条线有刚好两点呢?没有的这样的例子。Dirac猜想在平面上若有n点,则有至少有n/2条线有刚好两点。

可惜这个猜想是不对的。但截至2006年,已知有两个反例:

  • 一个等边三角形的三个顶点、各边的中点和三角形中心,共有7点,但只有三条线有刚好两点。
  • 两个大小相等的正五边形,其中一边重叠。取这两个五边形的所有顶点(8点),加上重叠边的中点(1点),再加上取四组平行线上的无限远点(4点)。该四组平行线分别是跟重叠边成0°、90°、+36°和-36°的。在经过这13点的线中,只有6条线有刚好两点。

虽然Dirac的猜想不对,但有较弱的结果:在n点中,至有有条线刚好有两点通过。

Beck定理则说明了,存在常数C,K,使以下其中一个论述为真:

  • 有一条线有n/C点。
  • 至少有n2/K条线,线上至少有两点。

历史

1893年,詹姆斯·约瑟夫·西尔维斯特将此问题提出。保罗·艾狄胥也曾在1943年独立提出这个定理。1944年蒂博尔·加莱发表了的证明。 不过,1940年E. Melchior已证明了。

参考

  1. ^ Dirac, G. Collinearity properties of sets of points. Quart. J. Math. 1951, 2: 221–227.
  2. ^ Crowe, D. W.; McKee, T. A. Sylvester's problem on collinear points. Mathematics Magazine. 1968, 41 (1): 30–34 [2016-05-02]. (原始内容存档于2016-10-05).
  3. ^ Csima, J.; Sawyer, E. There exist 6n/13 ordinary points. Discrete & Computational Geometry. 1993, 9: 187–202. doi:10.1007/BF02189318.
  4. ^ Sylvester, J. J. Mathematical question 11851. Educational Times. 1893, 59: 98.
  5. ^ Erdős, P. Problem 4065. American Mathematical Monthly. 1943, 50: 65 [2016-05-02]. (原始内容存档于2019-12-20).
  6. ^ Steinberg, R.; Buck, R. C.; Grünwald, T. (Tibor Gallai); Steenrod, N. E. Three point collinearity (solution to problem 4065). American Mathematical Monthly. 1944, 51: 169–171 [2016-05-02]. (原始内容存档于2019-12-10).
  7. ^ Melchior, E. Über Vielseite der projektiven Ebene. Deutsche Math. 1940, 5: 461–475.
  • Borwein, P.; Moser, W. O. J. A survey of Sylvester's problem and its generalizations. Aequationes Mathematicae. 1990, 40 (1): 111–135. doi:10.1007/BF02112289.
  • Kelly, L. M.; Moser, W. O. J. On the number of ordinary lines determined by n points. Canad. J. Math. 1958, 10: 210–219.
  • Mukhopadhyay, A.; Agrawal, A.; Hosabettu, R. M. On the ordinary line problem in computational geometry. Nordic Journal of Computing. 1997, 4 (4): 330–341.

本页面最后更新于2021-06-18 18:40,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器