西爾維斯特-加萊定理

维基百科,自由的百科全书
跳转至: 导航搜索

西爾維斯特–加萊定理(Sylvester–Gallai theorem)說明若在平面上有有限數目的,點的數目多於2,它們不是全部共線,就是有一條線上剛好有兩點。也就是说,如果过任意两点的直线都必过第三点,则所有的点共线。

這個定理在無限點的情況並不成立,可以考慮格點{\Bbb Z} \times {\Bbb Z}

證明[编辑]

Sylvester-Gallai theorem.png

以下使用無窮遞降法

  1. 在平面上有有限多點,若它們都共線,那我們就找到想要的東西;若非,定義一條「連線」為一條連起來至少有兩點的線。設I為一條連線,因為不是所有點都共線,至少有一點P不屬於I。
  2. 若I不是有剛好兩點,I便至少有三點,稱為A,B,C。不失一般性,設B在A和C之間,因為\angle ABP + \angle CBP = \pi,所以兩隻角不可能同時是鈍角。不失一般性設\angle ABP不是鈍角,而是銳角或直角。
  3. 設連結C和P的線為m,m是不包括B的連線,而且B和m的距離比P和I的距離小。
  4. 以B和m取代第二步的P和I。這個動作不可能無窮次重複,因為若能無窮次重複,連線和某一不在連線上的點距離便會得出一個無窮遞降的序列,但只有有限個點和有限條連線,這是不可能的。因此,至少有一條線剛好有兩點。

推廣[编辑]

Dirac的猜想的反例。

這個定理說明了在所有點至少有一條線有剛好兩點。在甚麼情況下,只有一條線有剛好兩點呢?沒有的這樣的例子。Dirac猜想在平面上若有n點,則有至少有n/2條線有剛好兩點。[1]

可惜這個猜想是不對的。但截至2006年,已知有兩個反例:

  • 一個等邊三角形的三個頂點、各邊的中點和三角形中心,共有7點,但只有三條線有剛好兩點。
  • 兩個大小相等的正五邊形,其中一邊重疊。取這兩個五邊形的所有頂點(8點),加上重疊邊的中點(1點),再加上取四組平行線上的無限遠點(4點)。該四組平行線分別是跟重疊邊成0°、90°、+36°和-36°的。在經過這13點的線中,只有6條線有剛好兩點。[2]

雖然Dirac的猜想不對,但有較弱的結果:在n點中,至有有\lceil \frac{6n}{13} \rceil條線剛好有兩點通過。[3]

Beck定理則說明了,存在常數C,K,使以下其中一個論述為真:

  • 有一條線有n/C點。
  • 至少有n2/K條線,線上至少有兩點。

歷史[编辑]

1893年,詹姆斯·約瑟夫·西爾維斯特將此問題提出[4]保羅·艾狄胥也曾在1943年獨立提出這個定理。[5]1944年蒂博爾·加萊發表了的證明[6]。 不過,1940年E. Melchior已證明了。[7]

參考[编辑]

  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. 
  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. 
  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. 
  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.