Robertsova věta o trojúhelníku

Robertsova věta o trojúhelnících říká, že mezi kusy, do kterých přímky v obecné poloze rozřezávají rovinu, je alespoň trojúhelník. $n$ $n-2$

Věta je známá svou jednoduchou formulací a velkým množstvím chybných řešení. Zejména Roberts, po kterém je teorém pojmenován, podal chybný důkaz. Tento problém vyřešil Shannon až po 90 letech od okamžiku nastavení.

Formulace

Nechť jsou v rovině přímky v obecné poloze, to znamená, že žádné dvě nejsou rovnoběžné a žádné tři se neprotínají v jednom bodě. Potom mezi polygonálními oblastmi, do kterých tyto čáry protínají rovinu, je alespoň trojúhelník. $n$ $n-2$

Historie

Otázku formuloval a vyřešil Roberts v roce 1889.
- V roce 1972 Branko Grünbaum upozornil na chybu v důkazu.
V roce 1979 Shannon podal první důkaz teorému.
Na počátku 80. let se problém stal populárním v matematických kruzích v SSSR.
V roce 1985 podal Alexej Kanel-Belov elegantní elementární důkaz pomocí lineární algebry , který byl publikován až v roce 1992.
V roce 1998 předložili Stefan Felsner a Klaus Kriegel jednoduchý čistě kombinatorický důkaz
- Jejich důkaz funguje také pro pseudolinkové konfigurace .

O důkazech

Standardní chybou je pokusit se dokázat, že přidáním jednoho řádku do konfigurace se počet trojúhelníků zvýší alespoň o 1, a tím dokázat větu indukcí na . Je snadné dokázat, že přidáním jednoho řádku se počet trojúhelníků nezmenšuje, ale ne vždy se k jejich počtu přidá 1. $n\geq 3$ $n$

Myšlenka Kanel-Belov je následující. Pokud je počet trojúhelníků menší než , pak lze pomocí standardní lineární algebry zafixovat dvě úsečky a zbytek posunout rovnoběžně tak, aby obvody všech trojúhelníků zůstaly stejné. Při takovém pohybu nevznikají žádné nové trojúhelníky a ty staré nemohou „umřít“. Pomocí takového pohybu lze zredukovat konfiguraci čar na jednodušší případ, ve kterém není důkaz obtížný. $n-2$ $n-2$

Myšlenka Felsnera a Kriegela je následující. Do každého kusu mezistěny zasadíme z každé strany květinu, u které je součet úhlů k ní přiléhajících . Všimněte si, že na každé straně je zasazena přesně jedna květina, takže počet květin je . Dále si všimneme, že v každém trojúhelníku jsou právě tři květiny a v ohraničeném mnohoúhelníku jiném než trojúhelník jsou nanejvýš dvě květiny. Indukcí na dostaneme, že počet ohraničených polygonů oddílu je roven $</pi$ $n\cdot (n-2)$ $n$ ${\tfrac {1}{2}}\cdot (n-2)\cdot (n-1)$ .

Pokud tedy označíme počet trojúhelníků jako , dostaneme

t

(n-2)\cdot (n-1)+t\geq n\cdot (n-2)

, odkud žádané bezprostředně následuje .

t\geq n-2

Variace a zobecnění

Výrok zůstává pravdivý, pokud v konfiguraci nejsou žádné rovnoběžné čáry a ne všechny čáry procházejí stejným bodem.
Podobný problém na projektivní rovině je jednodušší, alespoň trojúhelníky jsou vyříznuty čarami. Tento odhad je přesný pro . Důkaz podal Friedrich Levi v roce 1926, je založen na skutečnosti, že každá linie ohraničuje nejméně tři trojúhelníky. $n$ $n$ $n\geq 4$
Mezi kusy -dimenzionálního euklidovského prostoru, do kterého je rozdělen na nadroviny v obecné poloze, existují alespoň simplices . $d$ $n$ $nd$

Viz také

Literatura

A. Kanel, A. Kovaldži. Trojúhelníky a katastrofy // Kvant . - 1992. - č. 11 . - S. 42-50 . (Ruština)
A. Ya, Belov. K problému kombinatorické geometrie // Uspekhi Mat . - 1992. - T. 47 , č. 3 (285) . — S. 151–152 . (Ruština)
B. Grunbaum . Kolik trojúhelníků? (anglicky) // Geombinatorials . - 1998. - Sv. 8 , č. 1 . - S. 154-159 .
B. Grunbaum . Aranžmá a spready . - 1972. - iv + 114 s.
S. Felsner, K. Kriegel. Trojúhelníky v euklidovských uspořádáních // Diskrétní výpočet. Geom.. - 1999. - Sv. 22 , č. 3 . - str. 429-438 .
F. Levi. Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade (německy) // Ber. Matematika-fyz. Kl. Sachsová. Akad. Wiss. - 1926. - Bd. 78 . - S. 256-267 .
S. Roberts. Na obrazcích tvořených průsečíky soustavy přímek v rovině a na analogických vztazích v prostoru tří rozměrů // Proc . Londýnská matematika. Soc.. - 1889. - Sv. 19 . — S. 405–422 .
RW Shannon. Jednoduché buňky v uspořádání nadrovin // Geom . Dedicata . - 1979. - Sv. 8 . — S. 179–187 .