XXIII OM - III - Zadanie 2

Na płaszczyźnie danych jest $ n > 2 $ punktów, z których żadne trzy nie ją współliniowe. Udowodnić, że najkrótsza spośród łamanych zamkniętych przechodzących przez te punkty jest łamaną zwyczajną.

Rozwiązanie

Przypomnijmy określenie łamanej zwyczajnej: Łamaną zamkniętą o kolejnych wierzchołkach $ W_1, W_2, \ldots, W_n, W_{n+1} $, gdzie $ W_{n+1} = W_1 $, nazywamy łamaną zwyczajną, jeżeli odcinki domknięte $ \overline{W_iW_{i+1}} $ i $ \overline{W_jW_{j+1}} $ są rozłączne dla $ 1 \leq i,j \leq n $, $ 1 <j - i <<br /> n - 1 $.

Niech żadne trzy z punktów $ A_1, A_2, \ldots, A_n $ na płaszczyźnie nie będą współliniowe i niech $ A_{n+1} = A_1 $. Przypuśćmy, że łamana zamknięta $ L $ przechodząca kolejno przez punkty $ A_1, A_2, \ldots, A_n, A_{n+1} $ jest najkrótsza i nie jest łamaną zwyczajną. Jeżeli $ i \ne j $, $ 1 \leq i, j \leq n $, to niech $ L (A_i, A_j) $ będzie częścią łamanej $ L $ o początku w punkcie $ A_i $ i zawierającą kolejno punkty $ A_{i+1}, A_{i+2}, \ldots, A_j $.

Dla $ i = 1, 2, \ldots, n $ mamy $ L(A_i, A_{i+1}) = \overline{A_i A_{i+1}} $, ponieważ najkrótszą łamaną łączącą dwa punkty jest odcinek.

Z przypuszczenia, że $ L $ nie jest łamaną zwyczajną wynika, że istnieją takie liczby $ i $, $ j $, że

\[<br /> (1) \qquad 1 \leq i, j \leq n \ \textrm{oraz}\ 1 < j - i < n - 1<br /> \]

oraz łamana $ L(A_i, A_{i+1}) $ i $ L(A_j, A_{j+1}) $ mają punkt wspólny $ P $ (rys. 15). Z warunków (1) wynika, że punkty $ A_i, A_{i+1}, A_j, A_{j+1} $ są różne. Wobec tego punkt $ P $ należy do wnętrza każdego z odcinków $ \overline{A_iA_{i+1}} $, $ \overline{A_jA_{j+1}} $; z założenia bowiem żadne trzy z punktów $ A_1, A_2, \ldots, A_n $ nie leżą na jednej prostej.

Ponieważ w trójkącie długość dowolnego boku jest mniejsza niż suma długości boków pozostałych, więc

\[<br /> A_iA_j < A_iP + PA_j \ \textrm{oraz}\ A_{i+1}A_{j+1} < A_{i+1}P + PA_{j+1}.<br /> \]

Stąd

\[<br /> A_1A_j + A_{i+1}A_{j+1} < A_iA_{i+1} + A_jA_{j+1}.<br /> \]

Wobec tego łamana zamknięta $ L' $ złożona kolejno z łamanych $ L(A_{j+1}, A_i) $, $ \overline{A_iA_j} $, $ L(A_{i+1}, A_j) $, $ \overline{A_{i+1}A_{j+1}} $ przechodzi przez punkty $ A_1, A_2, \ldots, A_n $ i jest krótsza od łamanej zamkniętej $ L $, która składa się kolejno z łamanych $ L(A_{j+1}, A_i) $, $ \overline{A_iA_{i+1}} $, $ L(A_{i+1}, A_j) $, $ \overline{A_jA_{j+1}} $. Uzyskana sprzeczność dowodzi, że najkrótsza łamana zamknięta przechodząca przez punkty $ A_1, A_2, \ldots, A_n $ jest łamaną zwyczajną.

Uwaga. Łatwo dowieść, że istnieje łamana zamknięta najkrótsza przechodząca przez dane punkty $ A_1, A_2, \ldots, A_n $. Mianowicie, jeżeli łamana przechodzi kolejno przez punkty $ A_i $ i $ A_j $, to część łamanej zawarta między tymi punktami jest niekrótsza od odcinka $ \overline{A_iA_j} $ (odcinek bowiem jest najkrótszą łamaną łączącą dwa punkty). Zatem, by znaleźć łamaną najkrótszą przechodzącą przez punkty $ A_1, A_2, \ldots, A_n $, wystarczy rozważać łamane złożone z odcinków $ \overline{A_iA_j} $. Odcinków takich jest liczba skończona. Zatem i łamanych zamkniętych wyznaczonych przez takie odcinki jest tylko liczba skończona. Istnieje więc wśród tych łamanych najkrótsza.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź