XIX OM - II - Zadanie 6

Na płaszczyźnie obrano $ n \geq 3 $ punktów nie leżących na jednej prostej. Prowadząc proste przez każde dwa z tych punktów otrzymano $ k $ prostych. Dowieść, że $ k \geq n $.

Rozwiązanie

Udowodnimy najpierw twierdzenie:

Jeżeli $ n \geq 3 $ i $ A_1, A_2, \ldots, A_n $ są punktami płaszczyzny nie leżącymi na jednej prostej, to istnieje taka prosta, która zawiera dwa i tylko dwa z tych punktów.

Dowód. Z założenia wynika, że pewne trójki punktów są niewspółliniowe. Gdy $ A_i $, $ A_k $, $ A_l $ jest taką trójką, niech wówczas $ d_{ikl} $ oznacza odległość punktu $ A_i $ od prostej $ A_kA_l $. Zbiór liczb dodatnich $ d_{ikl} $ jest skończony, więc istnieje w nim liczba, od której nie ma w tym zbiorze mniejszej. Możemy przyjąć, że liczbą tą jest np. $ d_{123} $, gdyż można to uzyskać przez odpowiednie oznaczenie punktów (rys. 15).

Prosta $ A_2A_3 $ nie zawiera wówczas żadnego z pozostałych punktów $ A_i $. Gdyby bowiem leżał na niej np. punkt $ A_4 $, wówczas dwa z punktów $ A_2 $, $ A_3 $, $ A_4 $, np. punkty $ A_3 $ i $ A_4 $ znajdowałyby się po tej samej stronie prostopadłej z punktu $ A_1 $ do prostej $ A_2A_3 $, a wtedy zachodziłaby jedna z nierówności

\[<br />
d_{314} < d_{123} \textrm{ lub } d_{413} < d_{123},<br />
\]

co byłoby sprzeczne z określeniem liczby $ d_{123} $.

Opierając się na powyższym twierdzeniu, dowód twierdzenia podanego w tekście zadania uzyskujemy łatwo przez indukcję.

Gdy $ n = 3 $, teza twierdzenia jest prawdziwa, gdyż wówczas $ k = 3 $. Przypuśćmy, że teza twierdzenia jest prawdziwa dla pewnego naturalnego $ n \geq 3 $. Niech $ Z= \{ A_1,A_2,\ldots,A_n, A_{n + 1}\} $ będzie zbiorem punktów płaszczyzny, nie leżących na jednej prostej i niech $ A_1A_{n+1} $ będzie taką prostą, która zawiera dokładnie dwa spośród punktów zbioru $ Z $. Z założenia wynika, że co najmniej w jednym ze zbiorów $ n $-punktowych $ Z_1 = \{A_1, A_2, \ldots, A_n\} $ i $ Z_2 = \{ A_2, A_3,\ldots, A_{n + 1}\} $ istnieją punkty niewspółliniowe. Niech na przykład punkty zbioru $ Z $ nie leżą na jednej prostej. Według założenia indukcyjnego liczba prostych poprowadzonych przez każde dwa punkty zbioru $ Z_1 $ jest co najmniej równa $ n $. Ponieważ prosta $ A_1A_{n+1} $ do tych prostych nie należy, gdyż przechodzi tylko przez jeden punkt zbioru $ Z_1 $, więc liczba prostych poprowadzonych przez każde dwa punkty zbioru $ Z $ jest co najmniej równa $ n + 1 $. Dowód indukcyjny twierdzenia został przeprowadzony.

Komentarze

Dodaj nową odpowiedź