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

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

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

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

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

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

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

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

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

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

Пряме доведення знайшов через пів століття Келлі^[en].

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

Зауваження

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