W przestrzeni wybrano 2n punktów...

piwcuk · Post autor: **piwcuk** » 16 kwie 2006, o 15:26

Jest to jedno z zadań przygotowawczych do Podlaskiego Konkursu Matematycznego 2006 dla klas II.

W przestrzeni wybrano 2n punktów tak, że żadne cztery nie leżą w jednej płaszczyźnie. Następnie połączono pewne punkty tworząc \(\displaystyle{ n^{2}+1}\) odcinków. Wykazać, że pewne trzy odcinki tworzą trójkąt.

TomciO · Post autor: **TomciO** » 17 kwie 2006, o 02:03

Wynika to bezposrednio z Tw. Turana.

piwcuk · Post autor: **piwcuk** » 17 kwie 2006, o 11:44

Jeśli chodzi o te twierdzenie to internet jest dość ubogi w informacje o nim. Znalazłem tylko wzór i treść twierdzenia, bez poparcia przykladem:

twierdzenie Turana:
jezeli graf ma \(\displaystyle{ n}\) wierzcholkow i nie ma w nim \(\displaystyle{ m+1}\)elementowej kliki, to liczba wszystkich krawedzi w grafie nie przekracza \(\displaystyle{ \frac{(m-1)n^{2}-r(m-r)}{2m}}\), gdzie \(\displaystyle{ r}\) jest reszta z dzielenia \(\displaystyle{ n}\) przez \(\displaystyle{ m}\)

jednak nie rozumiem tego twierdzenia ani nie widze zwiazku z zadaniem. Moglbys mi cos przyblizyc?

TomciO · Post autor: **TomciO** » 17 kwie 2006, o 16:38

Tak naprawde te punkty tworza pelnoprawny graf, w tej wersji wez \(\displaystyle{ m=2}\) ;>.
I masz dokladnie teze - bo jak wstawisz to Ci wyjdzie cos mniejszego niz \(\displaystyle{ n^2+1}\). Jakby jeszcze cos bylo niejasnego to pytaj.
Swoja droga to bylo tez na Putnamie w ktoryms tam roku (96?) i jeszcze chyba na conajmniej paru innych konkursach.

piwcuk · Post autor: **piwcuk** » 17 kwie 2006, o 17:29

hm.. dalej niejasne..

jezeli wierzchołków jest 2n i m=2 (dlaczego?) oraz r=0 (reszta z dzielenia liczby 2n przez 2 musi byc rowna 0 )to ze wzoru wynika:

\(\displaystyle{ \frac{(2-1)(2n)^{2}-0*(2-0)}{2*2)} = n^{2}}\)

faktycznie jest to mniejsze niż \(\displaystyle{ n^{2}+1}\) tylko dlaczego m=2?

Aha i może znasz dowód tego twierdzenia lub wiesz czy mogę go gdzieś znaleźć?

TomciO · Post autor: **TomciO** » 17 kwie 2006, o 17:35

To twierdzenie jest prawdziwe dla kazdego \(\displaystyle{ m}\) (oczywiscie kazdego sensownego) wiec sobie wstawiasz takie jak Ci pasuje. Generalnie gdyby zapomniec o ogolniejszej wersji to Tw. Turana dla \(\displaystyle{ m=2}\) brzmialo by tak:
Jezeli graf ma n wierzcholkow i nie ma w nim trzech wierzcholkow, ktore tworza trojkat to ma conajwyzej ... krawedzi.
Klika jakby co to jest podgraf bedacy grafem kompletnym (czy tam pelnym po angielsku jest complete).

Dowodu zaraz poszukam...

piwcuk · Post autor: **piwcuk** » 17 kwie 2006, o 17:43

skapowałem, dzięki.. jak znajdziesz dowód będę wdzięczny bo ja nie znalazłem :]

edit/
aha i jeszcze jedno.. potrafilbys podac przyklad jakiegos innego zadania z zastosowaniem tego twierdzenia?