Roberts-háromszög tétel

Roberts háromszög-tétele kimondja, hogy azon darabok között, amelyekbe az általános helyzetben lévő egyenesek síkot vágnak, van legalább egy háromszög. $n$ $n-2$

A tétel egyszerű megfogalmazásáról és nagyszámú hibás megoldásáról híres. Különösen Roberts, akiről a tételt elnevezték, téves bizonyítékot adott. Ezt a problémát Shannon csak a beállítás pillanatától számított 90 év elteltével oldotta meg.

Megfogalmazás

Legyenek a síkban általános helyzetű egyenesek, vagyis ne legyen kettő párhuzamos, és három se metszi egymást egy pontban. Ekkor a sokszögterületek között, amelyekbe ezek a vonalak a síkot vágják, van legalább egy háromszög. $n$ $n-2$

Történelem

A kérdést Roberts fogalmazta meg és oldotta meg 1889-ben.
- 1972-ben Branko Grünbaum rámutatott egy hibára a bizonyításban.
1979-ben Shannon megadta a tétel első bizonyítását.
Az 1980-as évek elején a probléma népszerűvé vált a Szovjetunió matematikai köreiben.
Alekszej Kanel-Belov 1985- ben adott egy elegáns elemi bizonyítást lineáris algebrával , amely csak 1992-ben jelent meg.
1998-ban Stefan Felsner és Klaus Kriegel egy egyszerű, tisztán kombinatorikus bizonyítást mutatott be.
- Bizonyításuk pszeudovonal konfigurációkra is működik .

A bizonyítékokról

A standard hiba az, hogy megpróbáljuk bebizonyítani, hogy egy sor hozzáadása a konfigurációhoz legalább 1-gyel növeli a háromszögek számát, és így bizonyítjuk a tételt indukcióval -on . Könnyen bebizonyítható, hogy egy sor hozzáadásával nem csökken a háromszögek száma, de nem mindig ad hozzá 1-et a számukhoz. $n\geq 3$ $n$

Kanel-Belov ötlete a következő. Ha a háromszögek száma kisebb, mint , akkor standard lineáris algebrai érveléssel rögzíthetünk két egyenest, a többit pedig párhuzamosan mozgathatjuk úgy, hogy az összes háromszög kerülete azonos maradjon. Egy ilyen mozgással nem alakulnak ki új háromszögek, és a régiek nem tudnak „meghalni”. Egy ilyen mozgás segítségével a vonalak konfigurációja egyszerűbb esetre redukálható, amelyben a bizonyítás nem nehéz. $n-2$ $n-2$

Felsner és Kriegel ötlete a következő. A válaszfal minden darabjába mindkét oldalára ültetünk egy virágot, amelyre a vele szomszédos szögek összege . Vegye figyelembe, hogy pontosan egy virágot ültetnek mindkét oldalra, ezért a virágok száma . A továbbiakban megjegyezzük, hogy minden háromszögben pontosan három virág van, és a háromszögtől eltérő korlátos sokszögben legfeljebb két virág található. Az indukcióval azt kapjuk, hogy a partíció korlátos sokszögeinek száma egyenlő $</pi$ $n\cdot (n-2)$ $n$ ${\tfrac {1}{2}}\cdot (n-2)\cdot (n-1)$ .

Tehát, ha a háromszögek számát mintával jelöljük , akkor azt kapjuk

t

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

, ahonnan azonnal következik a kívánt .

t\geq n-2

Változatok és általánosítások

Az állítás igaz marad, ha a konfigurációban nincsenek párhuzamos egyenesek, és nem minden egyenes halad át ugyanazon a ponton.
A projektív síkon egy hasonló probléma egyszerűbb , legalább a háromszögeket vonalak vágják ki. Ez a becslés pontosan erre vonatkozik . A bizonyítékot Friedrich Levi adta 1926-ban, azon a tényen alapul, hogy minden vonal legalább három háromszöggel határos. $n$ $n$ $n\geq 4$
A -dimenziós euklideszi tér azon darabjai között, amelyekbe általános helyzetben hipersíkra van osztva , vannak legalább egyszerűségek . $d$ $n$ $nd$

Lásd még

Irodalom

A. Kanel, A. Kovaldzhi. Háromszögek és katasztrófák // Kvant . - 1992. - 11. sz . - S. 42-50 . (Orosz)
A. Ya. Belov. A kombinatorikus geometria problémájáról // Uspekhi Mat . - 1992. - T. 47 , 3. szám (285) . – S. 151–152 . (Orosz)
B. Grunbaum . Hány háromszög? (angol) // Geombinatorials . - 1998. - Vol. 8 , sz. 1 . - 154-159 . o .
B. Grunbaum . Elrendezések és szórások . - 1972. - iv + 114 p.
S. Felsner, K. Kriegel. Háromszögek euklideszi elrendezésben // Discrete Comput. Geom.. - 1999. - Vol. 22 , sz. 3 . - P. 429-438 .
F. Levi. Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade (német) // Ber. Math.-Phys. Kl. Sachs. Akad. Wiss. - 1926. - Bd. 78 . - S. 256-267 .
S. Roberts. Egy egyenes rendszer síkbeli metszéspontjai által alkotott ábrákról és analóg összefüggésekről a háromdimenziós térben // Proc . London Math. Szoc.. - 1889. - 1. köt. 19 . — P. 405–422 .
RW Shannon. Egyszerű cellák hipersíkok elrendezésében // Geom . Dedicata . - 1979. - 1. évf. 8 . — P. 179–187 .