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

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

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

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

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

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

Якщо на площині дано таку скінченну множину прямих, що через будь-яку точку перетину двох даних прямих проходить ще одна з них, то всі вони проходять через одну точку або паралельні.|} Доведення двоїстого переформулювання Нехай одна з даних прямих $\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$ і діючи далі аналогічно, отримуємо суперечність зі скінченністю множини. ■ Пряме доведення Пряме доведення знайшов через пів століття Келлі Припустимо неколінеарність точок даної множини. Вибираємо пару: її точка $A$ і пряма $d$, для якої відстань від $A$ до $d$ мінімальна додатна; така пара існує з огляду на скінченність множин точок і з'єднувальних прямих. Позначимо на $d$ три точки: $B$, $C$ і $D$ з даної множини. Нехай точка $P$ є основою перпендикуляра, опущеного з $A$ на $d$. Не зменшуючи загальності, можна вважати, що точки $P$, $B$ і $C$ розташовані на $d$ в зазначеному порядку; при цьому точки $P$ і $B$ можуть збігатися. Тоді відстань від точки $B$ до прямої $AC$ додатна і менша, ніж від $A$ до $d$. Суперечність. ■ Зауваження Оскільки в доведенні ніяк не використовується умова, що всі точки лежать у площині, теорема Сильвестра поширюється на множини в евклідовому просторі довільної розмірності. Див. також Теорема де Брейна — Ердеша