XVI OM - III - Zadanie 3

Zawody matematyczne:

XXVI OM, 1974-1975

Etap:

Na okręgu obrano $n > 2$ punktów i każdy z nich połączono odcinkiem z każdym innym. Czy można wykreślić wszystkie te odcinki jednym ciągiem, tzn. tak, żeby koniec pierwszego odcinka był początkiem drugiego, koniec drugiego - początkiem trzeciego itd., i żeby przy tym koniec ostatniego odcinka był początkiem pierwszego?

Rozwiązanie

Aby ułatwić wysłowienie, wprowadzimy pewną umowę. Niech $Z$ będzie skończonym zbiorem punktów okręgu (warunek, że punkty zbioru Z leżą na okręgu można zastąpić założeniem słabszym, że żadne $3$ punkty tego zbioru nie leżą na jednej prostej. Ta sama uwaga stosuje się do dalszego ciągu rozwiązania). Jeżeli łamana zamknięta, której wierzchołkami są punkty zbioru $Z$ , ma tę własność, że w ciągu kolejnych boków łamanej każdy odcinek łączący dwa punkty zbioru $Z$ występuje jeden i tylko jeden raz, to łamaną taką nazwiemy $L(Z)$ .

Przypuśćmy, że dla pewnego zbioru $Z$ składającego się z $n \geq 3$ punktów okręgu istnieje łamana $L(Z)$ . W każdym z punktów zbioru $Z$ schodzi się wówczas $n- 1$ boków łamanej. Wykreślając łamaną jednym ciągiem, dochodzimy do każdego jej wierzchołka tyle samo razy, ile razy zeń wychodzimy; liczba $n - 1$ jest zatem parzysta, czyli $n$ jest liczbą nieparzystą. Łamana $L (Z)$ nie może zatem istnieć, gdy $n$ jest liczbą parzystą. Dowiedziemy, że gdy $n$ jest nieparzyste, wtedy łamana $L (Z)$ istnieje (mogą oczywiście istnieć różne łamane $L (Z)$ dla tego samego zbioru $Z$ ).

\spos{1} (metoda indukcji). Niech $n = 2m + 1$ ( $m$ - liczba naturalna). Dla $m = 1$ , tj. dla zbioru trzech punktów $A_1$ , $A_2$ , $A_3$ twierdzenie jest prawdziwe, żądaną łamaną jest $A_1A_2A_3A_1$ .

Przypuśćmy, że twierdzenie jest prawdziwe, gdy $m = k - 1$ , tj. gdy zbiór ma $2k - 1$ punktów ( $k$ - liczba naturalna $\geq 2$ ); udowodnimy, że jest ono wówczas prawdziwe, gdy $m = k$ , tj. gdy zbiór ma $n = 2k + 1$ punktów.

Weźmy pod uwagę zbiór $Z$ składający się z punktów $A_1A_2, \ldots, A_{2k-1}, A_{2k}, A_{2k+1}$ okręgu i niech $U$ oznacza zbiór zawierający tylko punkty $A_1, A_2, \ldots, A_{2k-1}$ . Według założenia indukcyjnego dla zbioru $U$ istnieje pewna łamana $L (U)$ .

Łatwo stwierdzić, że istnieje taka łamana zamknięta $K$ , której bokami są odcinki łączące każdy z punktów $A_1, A_2, \ldots, A_{2k-1}$ z punktami $A_{2k}$ i $A_{2k+1}$ oraz odcinek $A_{2k}A_{2k+1}$ , przy czym w ciągu kolejnych boków łamanej $K$ każdy z tych odcinków występuje tylko raz. Warunek ten spełnia na przykład łamana $K$ :

$<br /> A_1A_{2k}A_2A_{2k+1}A_3A_{2k}A_4A_{2k+1}A_5 \ldots A_{2k-1}A_{2k}A_{2k+1}A_1.<br />$

Zauważmy, że bokami łamanej $K$ są wszystkie te i tylko te spośród odcinków łączących punkty zbioru $Z$ , które nie są bokami łamanej $L (U)$ .

Tworzymy teraz z łamanych $L (U)$ i $K$ jedną łamaną zamkniętą w następujący sposób. Jako początek łamanej zamkniętej $L (U)$ obieramy punkt $A_1$ i przebiegamy tę łamaną dochodząc w końcu do punktu $A_1$ ; następnie przebiegamy łamaną $K$ zaczynając od punktu $A_1$ i kończąc znowu na punkcie $A_1$ . Otrzymujemy łamaną, której początkiem i końcem jest punkt $A_1$ , przy czym w ciągu kolejnych boków tej łamanej występuje każdy z odcinków łączących punkty zbioru $Z$ i to tylko jeden raz. Jest to więc poszukiwana łamana $L(Z)$ . Twierdzenie zostało udowodnione.