XVI OM - III - Zadanie 3

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.

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

Komentarze

Dodaj nową odpowiedź