XIX OM - II - Zadanie 6

Zawody matematyczne:

XIX OM, 1967-1968

Etap:

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.