szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 17 lis 2009, o 01:05 
Użytkownik

Posty: 1874
Lokalizacja: Lost Hope
Na początek kilka zadań:

1. Wykaż, że dowolny płaski wielokąt o obwodzie nieprzekraczającym 1 leży w pewnym kole o promieniu \frac 14.

Obrazek


2. Na płaszczyźnie \mathbb{R}^2 rozważmy prostokąty \{P_1,\ldots,P_n\} o wzajemnie równoległych parach boków o tej własności, że każde dwa mają niepuste przecięcie. Wykaż, że wówczas wszystkie prostokąty mają punkt wspólny.
Obrazek


3. Na płaszczyźnie ustalmy zbiór wypukły A. Niech zbiory wypukłe X_1,\ldots,X_n mają tę własność, że dla dowolnych trzech z nich istnieje przesunięcie zbioru A mające z tymi trzema niepuste przecięcie. Wykaż, że istnieje przesunięcie zbioru A mające niepuste przecięcie ze wszystkimi X_i.

Obrazek


4. Na płaszczyźnie rozważmy zbiór punktów p_1,\ldots p_n o tej własności, że każde trzy z nich leżą w pewnym kole o promieniu r. Wykaż, że istnieje koło o promieniu r, w którym leżą wszystkie punkty p_i.

Obrazek


5. Na płaszczyźnie rozważmy zbiór punktów p_1,\ldots p_n o tej własności, że każde dwa z nich są oddalone o niewięcej niż 1. Wykaż, że wszystkie punkty p_i leżą w pewnym kole o promieniu \frac 1{\sqrt 3}.

Obrazek


Zadania te łączy to, że można je rozwiązać stosując inne zadanie podobnego typu, wynik zwany twierdzeniem Helly'ego:

Twierdzenie (Eduard Helly, 1923): Niech X_1,\ldots,X_n, n\ge 3 będą wypukłymi zbiorami płaszczyzny o tej własności, że każde trzy z nich mają niepuste przecięcie. Wówczas przecięcie wszystkich X_i jest niepuste.

Dowód: Postępujemy indukcyjnie. Dla n=3 nie ma czego dowodzić. Dla kroku indukcyjnego rozważmy zbiór X_1\ldots,X_{n+1} spełniający założenia i przypuśćmy, że dla dowolnego i\in\{1,\ldots n+1\} zbiór Y_i=\bigcap_{j\neq i}X_j jest niepusty, znaczy zawiera element, który nazwiemy v_i. Rozważmy teraz punkty v_1,v_2,v_3,v_4. Albo są one wierzchołkami pewnego czworokąta wypukłego, albo jeden z tych punktów, powiedzmy v_4, leży w trójkącie (być może zdegenerowanym) rozpiętym na pozostałych.

Obrazek Obrazek


W drugim przypadku punkt v_4 leży w przecięciu zbiorów Y_1,\ldots Y_4, zaś w pierwszym punkt wystarczy rozważyć punkt v przecięcia przekątnych czworokąta v_1v_2v_3v_4, który leży w przecięciu Y_1,\ldots,Y_4, czyli w zbiorze \bigcap_{j=1}^{n+1}X_j. A to jest teza \square.

Przejdźmy do rozwiązań zadań:

2. Na mocy twierdzenia Helly'ego wystarczy pokazać, że dowolne trzy prostokąty mają niepuste przecięcie. Wybieramy osie układu współrzędnych rownoległe do boków prostokątów. Odcinki będące rzutami dowolnych trzech prostokątów na oś OX mają niepuste przecięcie, powiedzmy zawierające punkt x. Podobnie otrzymujemy punkt y na osi OY.

Obrazek przepadł na ImageShack.

Wówczas punkt (x,y) leży w przecięciu tych trzech prostokątów i argument zkończony \square.

3. Niech \sigma(X) oznacza środek ciężkości zbioru X. Dla każdego i\in\{1,2,\ldots n\} rozważmy zbiór Y_i taki, że dla każdego przesunięcia t:

t(A)\cap X_i \Leftrightarrow \sigma(t(A))\in Y_i

Obrazek


to znaczy zbiór Y_i jest zbiorem środków ciężkości przesunięć zbioru A mających niepuste przecięcie z X_i. Zbiory Y_i spełniają założenia twierdzenia Helly'ego, wybierzmy więc punkt v\in\bigcap Y_i. Szukane przesunięcie to takie, że punkt v jest środkiem ciężkości zbioru A\square.

4. Wystarczy w 3. za A wziąć koło o promieniu r\square.

5. Na mocy 4. wystarczy wykazać, że każde trzy punkty ze zbioru \{p_1,\ldots,p_n\} leżą w pewnym kole o promieniu \frac{1}{\sqrt 3}. Wystarczy więc pokazać, że dowolny trójkąt o bokach niedłuższych niż 1 leży w pewnym kole o promieniu \frac{1}{\sqrt 3}. Dla trójkąta rozwartokątnego wystarczy rozważyć koło, którego średnicą jest najdłuższy bok trójkąta, zaś da trójkątów nierozwartokątnych bierzemy koło opisane na trójkącie. Wybieramy parę a,\alpha - najdłuższy bok trójkąta, kąt naprzeciw tego boku.

Obrazek


Wówczas \alpha\ge\frac\pi 3 i z twierdzenia sinusów: 2R=\frac{a}{\sin\alpha}\le\frac{1}{\sin\frac\pi 3}\le\frac 2{\sqrt 3} \square.

1. Na mocy 4. wystarczy pokazać, że dowolne trzy wierzchołki wielokąta leżą w pewnym kole o promieniu \frac 14. Postępujemy podobnie do 5 \square.

Twierdzenie Helly'ego łatwo uogólnić na wyższe wymiary:

Twierdzenie: Niech X_1,\ldots,X_n, n\ge d+1 będą wypukłymi podzbiorami \mathbb{R}^d o tej własności, że każde d+1 z nich ma niepuste przecięcie. Wówczas przecięcie wszystkich X_i jest niepuste.

Przydatna definicja: Wieloindeksem (lub n-wieloindeksem) nazwiemy dowolny podzbiór I\in\{1,\ldots,n\}. Wieloindeksy służą często do indeksowania obiektów geometrycznych w kompleksach łańcuchowych.

Oznaczenia:

\mbox{conv}(A) to najmniejszy zbiór wypukły zawierający A zwany również otoczką wypukłą zbioru A.

Dla skończonej rodziny zbiorów A_1,\ldots A_n oraz wieloindeksu I\subseteq\{1,\ldots,n\} przyjmijmy A_I=\bigcap_{j\in I} A_j.

[n]=\{1,\ldots, n\}. Oznaczenie stosowane w teorii kompleksów symplicjalnych.

Dowód naśladuje przypadek płaski, przy czym rolę układów czteropunktowych przejmują układy d+2 - punktowe, zaś niepustość przecięć takich układów wynika z:

Lemat (Radon): Niech a_1,\ldots,a_m\in\mathbb{R}^d, m\ge d+2. Istnieją wówczas rozłączne podzbiory I,J zbioru [m] takie, że

\mbox{conv}\{a_i:i\in I\}\cap\mbox{conv}\{a_j:j\in J\}\neq\emptyset.
.

Dowód lematu 2: Niech (x_i^1,\ldots,x_i^d) będą współrzędnymi punktu x_i.

Układ d+1 równań z m niewiadomymi t_i dla i\in[m]:

\begin{cases}\sum_{i=1}^mt_i=0 \\\\ \sum_{i=1}^mt_ia_i^r\mbox{ dla }r\in[d] \end{cases}

ma niezerowe rozwiązanie (t_1,\ldots,t_m), bo m\ge d+2. Niech więc:

I=\{i:t_i>0\}

J=\{j:t_j<0\}.

Zbiory I,J są niepuste na mocy pierwszego rownania, oczywiście rozłączne oraz po dodaniu pozostałych rownań stronami otrzymujemy:

\sum_{i\in I}r_ia_i+\sum_{j\in J}r_ja_j=0.

Oznaczywszy s=\sum_{i\in I}r_i=-\sum_{j\in J}r_j otrzymujemy więc:

\sum_{i\in I}\frac{r_i}sa_i=-\sum_{j\in J}\frac{r_j}sa_j=0

co kończy argument, bo lewa strona to kombinacja wypukła punktów \{x_i:i\in I\} a prawa to kombinacja wypukła punktów \{x_j:j\in J\} \square.

W końcu przechodzimy do dowodu twierdzenia: Dla n=d+1 nie ma czego dowodzić. Dalej przez indukcję. Przypuśćmy, że n\ge n+2 i każda n-1 - elementowa rodzina podbiorów zbioru \{X_1,\ldots,X_n\} ma niepuste przecięcie. Wybierzmy po jednym punkcie v_i z każdego zbioru X_{[n]\setminus\{i\}}. Na mocy lematu 2 istnieją rozłączne niepuste I,J\subseteq[n] oraz punkt z takie, że:

z\in\mbox{conv}\{v_i:i\in J\}\cap\mbox{conv}\{v_j:j\in J\}\subseteq X_{[n]\setminus I}\cap X_{[n]\setminus J}\subseteq X_{[n]}.

Tym samym argument został zamknięty \square.
Góra
Instytut Matematyczny, Uniwersytet Wrocławski
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Twierdzenie Talesa, Podobieństwo.  pawelekbielany  3
 Podzielność wielomianów i twierdzenie Bezouta  lpluski  1
 Czy to twierdzenie jest prawdziwe?  bienieck  5
 twierdzenie Darboux dla pochodnych  leszczu450  9
 Twierdzenie Lagrange'a - zadanie 8  Xandow  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) ParaRent.com