Теорема Сильвестра — Галлаї

Теорема Сильвестра — класичний результат комбінаторної геометрії про конфігурації прямих на площині.

Формулювання

На площині дано скінченне число точок, причому таке, що будь-яка пряма, яка проходить через дві з даних точок, містить ще одну дану точку. Тоді всі дані точки лежать на одній прямій.

Про доведення

Теорема Сильвестра знаменита тим, що її досить складно довести безпосередньо і при цьому просте доведення полягає в переході до її двоїстого переформулювання: Шаблон:Рамка Якщо на площині дано таку скінченну множину прямих, що через будь-яку точку перетину двох даних прямих проходить ще одна з них, то всі вони проходять через одну точку або паралельні. Шаблон:/рамка

Доведення двоїстого переформулювання

Нехай одна з даних прямих $\ell$ не проходить через одну з точок перетину $P$. Знайдемо точку перетину і пряму, для яких відстань менша, ніж від $P$ до $\ell$. Оскільки число перетинів скінченне, це дасть суперечність. Випадок, коли через $P$ проходить пряма, не паралельна $\ell$, зображено на малюнку. Якщо ж третя пряма, що проходить через $P$, паралельна до прямої $\ell$, то розглянемо трикутник $A^{\prime }{B}^{\prime }{P}^{\prime }$, середні лінії якого утворюють трикутник $ABP$, де $A$ і $B$ — точки перетину двох прямих, що проходять через $P$, з прямою $\ell$. Якщо третя пряма, що проходить через $A$, не перетинає відрізка $B{P}^{\prime }$, то відстань від точки $P$ до неї менша, ніж до $\ell$. Аналогічно, якщо третя пряма, що проходить через $B$, не перетинає відрізка $A{P}^{\prime }$, то відстань від точки $P$ до неї менша, ніж до $\ell$. Якщо ж третя пряма, що проходить через $A$, перетинає відрізок $B{P}^{\prime }$ і третя пряма, що проходить через $B$, перетинає відрізок $A{P}^{\prime }$, то виникає точка перетину цих прямих. Якщо вона не збігається з $P^{\prime }$, то вона ближче до прямої $\ell$, ніж $P$. Якщо ж вона збігається з $P^{\prime }$, то можна застосувати вищенаведене міркування до неї і прямої $\ell$. Виникне трикутник $P{P}^{″}{P}^{‴}$, середні лінії якого утворюють трикутник $AB{P}^{\prime }$. Замінюючи тепер у наших міркуваннях трикутник $ABP$ трикутником $P^{″}{P}^{\prime }A$ і діючи далі аналогічно, отримуємо суперечність зі скінченністю множини. ■

Пряме доведення

Пряме доведення знайшов через пів століття Шаблон:Iw

Припустимо неколінеарність точок даної множини. Вибираємо пару: її точка $A$ і пряма $d$, для якої відстань від $A$ до $d$ мінімальна додатна; така пара існує з огляду на скінченність множин точок і з'єднувальних прямих. Позначимо на $d$ три точки: $B$, $C$ і $D$ з даної множини. Нехай точка $P$ є основою перпендикуляра, опущеного з $A$ на $d$. Не зменшуючи загальності, можна вважати, що точки $P$, $B$ і $C$ розташовані на $d$ в зазначеному порядку; при цьому точки $P$ і $B$ можуть збігатися. Тоді відстань від точки $B$ до прямої $AC$ додатна і менша, ніж від $A$ до $d$. Суперечність. ■

Зауваження

Оскільки в доведенні ніяк не використовується умова, що всі точки лежать у площині, теорема Сильвестра поширюється на множини в евклідовому просторі довільної розмірності.

Див. також

• Конфігурація Сильвестра — Галлаї
• Теорема де Брейна — Ердеша