Roberts triangelsats

Roberts teorem om trianglar säger att bland de bitar i vilka räta linjer i allmän position skär ett plan, finns det åtminstone en triangel. $n$ $n-2$

Teoremet är känt för sin enkla formulering och ett stort antal felaktiga lösningar. Särskilt Roberts, som satsen är uppkallad efter, gav ett felaktigt bevis. Detta problem löstes av Shannon först efter 90 år från inställningsögonblicket.

Formulering

Låt det finnas linjer i planet i allmänt läge, det vill säga inga två är parallella och inga tre skär varandra i en punkt. Sedan bland de polygonala områdena i vilka dessa linjer skär planet, finns det åtminstone en triangel. $n$ $n-2$

Historik

Frågan formulerades och löstes av Roberts 1889.
- 1972 påpekade Branko Grünbaum ett fel i beviset.
1979 gav Shannon det första beviset för satsen.
I början av 1980-talet blev problemet populärt i matematiska kretsar i Sovjetunionen.
1985 gavs ett elegant elementärt bevis med linjär algebra av Alexei Kanel-Belov , det publicerades inte förrän 1992.
1998 presenterades ett enkelt rent kombinatoriskt bevis av Stefan Felsner och Klaus Kriegel
- Deras bevis fungerar också för pseudolinkonfigurationer .

Om bevis

Standardfelet är att försöka bevisa att om man lägger till en rad i konfigurationen ökar antalet trianglar med minst 1, och därmed bevisa satsen genom induktion på . Det är lätt att bevisa att att lägga till en rad inte minskar antalet trianglar, men det adderar inte alltid 1 till deras antal. $n\geq 3$ $n$

Idén med Kanel-Belov är följande. Om antalet trianglar är mindre än , då kan man genom standard linjär algebra resonemang fixa två linjer och flytta resten parallellt så att omkretsen av alla trianglar förblir densamma. Med en sådan rörelse bildas inga nya trianglar, och de gamla kan inte "dö". Genom att använda en sådan rörelse kan man reducera konfigurationen av linjer till ett enklare fall där bevisningen inte är svår. $n-2$ $n-2$

Idén med Felsner och Kriegel är följande. I varje del av skiljeväggen planterar vi en blomma på varje sida, för vilken summan av vinklarna intill den är . Observera att exakt en blomma planteras på varje sida, därför är antalet blommor . Längre in noterar vi att det i varje triangel finns exakt tre blommor, och i en annan avgränsad polygon än en triangel finns det högst två blommor. Genom induktion på får vi att antalet avgränsade polygoner i partitionen är lika med $</pi$ $n\cdot (n-2)$ $n$ ${\tfrac {1}{2}}\cdot (n-2)\cdot (n-1)$ .

Så, om vi betecknar antalet trianglar som , får vi

t

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

, varifrån det önskade omedelbart följer .

t\geq n-2

Variationer och generaliseringar

Påståendet förblir sant om det inte finns några parallella linjer i konfigurationen och inte alla linjer passerar genom samma punkt.
Ett liknande problem på det projektiva planet är enklare, åtminstone trianglar skärs ut av linjer. Denna uppskattning är exakt för . Beviset gavs av Friedrich Levi 1926, det är baserat på det faktum att varje linje gränsar till minst tre trianglar. $n$ $n$ $n\geq 4$
Bland de delar av det dimensionella euklidiska utrymmet där det är uppdelat i hyperplan i allmän position, finns det åtminstone förenklingar . $d$ $n$ $nd$

Se även

Litteratur

A. Kanel, A. Kovaldzhi. Trianglar och katastrofer // Kvant . - 1992. - Nr 11 . - S. 42-50 . (ryska)
A. Ja. Belov. Om ett problem med kombinatorisk geometri // Uspekhi Mat . - 1992. - T. 47 , nr 3 (285) . — S. 151–152 . (ryska)
B. Grunbaum . Hur många trianglar? (engelska) // Geombinatories . - 1998. - Vol. 8 , nr. 1 . - S. 154-159 .
B. Grunbaum . Arrangemang och uppslag . - 1972. - iv + 114 sid.
S. Felsner, K. Kriegel. Trianglar i euklidiska arrangemang // Discrete Comput. Geom.. - 1999. - Vol. 22 , nr. 3 . - s. 429-438 .
F. Levi. Die Teilung der projektiven Ebene durch Gerade oder Pseudogerade (tyska) // Ber. Math.-Fys. Kl. Sachs. Akad. Wiss. - 1926. - Bd. 78 . - S. 256-267 .
S. Roberts. På figurerna som bildas av skärningarna av ett system av räta linjer i planet och på analoga relationer i rymden av tre dimensioner // Proc . London Math. Soc.. - 1889. - Vol. 19 . — S. 405–422 .
RW Shannon. Enkla celler i arrangemang av hyperplan // Geom . Dedicata . - 1979. - Vol. 8 . — S. 179–187 .