XXXIII OM - II - Zadanie 6

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.

Komentarze

Dodaj nową odpowiedź