XXIII OM - III - Zadanie 2

Zawody matematyczne:

XXIII OM, 1971-1972

Etap:

III

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 < 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

$ (1) \qquad 1 \leq i, j \leq n \ \textrm{oraz}\ 1 < j - i < n - 1 $

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

$ A_iA_j < A_iP + PA_j \ \textrm{oraz}\ A_{i+1}A_{j+1} < A_{i+1}P + PA_{j+1}. $

Stąd

$ A_1A_j + A_{i+1}A_{j+1} < A_iA_{i+1} + A_jA_{j+1}. $

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.