XXXIII OM - II - Zadanie 6

Zawody matematyczne:

XXXIII OM, 1981-1982

Etap:

Dany jest takt skończony zbiór $B$ punktów przestrzeni, że każde dwie odległości między punktami tego zbioru są różne. Każdy punkt zbioru $B$ łączymy odcinkiem z najbliższym mu punktem zbioru $B$ . Otrzymamy w ten sposób zbiór odcinków, z których jeden (dowolnie wybrany) malujemy na czerwono, wszystkie pozostałe odcinki malujemy na zielono. Dowieść, że istnieją takie dwa punkty zbioru $B$ , których nie można połączyć łamaną złożoną z odcinków pomalowanych na zielono.

Rozwiązanie

Przypuśćmy, że odcinek $A_1A_2$ jest czerwony, pozostałe są zielone. Jeśli istniałaby łamana złożona z odcinków zielonych łącząca punkty $A_1$ i $A_2$ to istniałyby punkty $A_3, \ldots, A_n$ będące kolejnymi końcami odcinków tworzących tę łamaną. Poniższy zapis typu $A_i \to A_j$ czytamy ,,najbliższym punktowi $A_i$ elementem zbioru $B$ jest $A_j$ ''. Z tego, że narysowany jest odcinek $\overline{A_iA_j}$ wynika, że $A_i \to A_j$ albo $A_j \to A_i$ . Wobec założenia, że każde dwie odległości między punktami zbioru $B$ są różne, nie może dla $k \ne j$ zachodzić jednocześnie $A_i \to A_j$ oraz $A_i \to A_k$ . Wynika stąd, że musi być albo $A_1 \to A_2, A_2 \to A_3, \ldots, A_{n-1} \to A_n, A_n \to A_1$ , albo $A_1 \to A_n, A_n \to A_{n-1}, \ldots, A_3 \to A_2, A_2 \to A_1$ .

W obu przypadkach odległości kolejnych punktów spełniałyby odpowiednio sprzeczne nierówności.

$<br /> A_1A_2 > A_2A_3 > \ldots A_{n-1}A_n > A_nA_1 > A_1A_2<br />$

albo

$<br /> A_1A_2 < A_2A_3 < \ldots < A_{n-1}A_n < A_nA_1 < A_1A_2.<br />$

Wobec tego punkty $A_1$ i $A_2$ nie mogą być połączone łamaną złożoną z odcinków zielonych.

Uwaga. Ponieważ rozważane odcinki nie mają wspólnych punktów wewnętrznych, więc z powyższego rozwiązania wynika teza silniejsza od sformułowanej w zadaniu: Istnieją dwa punkty zbioru $B$ , których nie można połączyć łamaną złożoną z odcinków zawartych w sumie odcinków zielonych.