XXV OM - III - Zadanie 6

Podzielono $ n $-kąt wypukły przekątnymi na trójkąty w ten sposób, że
1° z każdego wierzchołka wychodzi parzysta liczba przekątnych,
2° żadne dwie przekątne nie mają wspólnych punktów wewnętrznych.
Udowodnić, że $ n $ jest podzielne przez 3.

Rozwiązanie

Udowodnimy najpierw

Lemat. Jeżeli $ F $ jest figurą na płaszczyźnie i za pomocą $ r $ prostych podzielono ją na części, to można te części tak pomalować dwoma kolorami, by każde dwie części mające odcinek wspólny miały różne kolory.

Dowód. Zastosujemy indukcję ze względu na $ r $. W przypadku $ r = 1 $ teza jest oczywista, ponieważ prosta dzieli płaszczyznę na dwie półpłaszczyzny. Części figury $ F $ zawarte w jednej półpłaszczyźnie malujemy jednym kolorem, a części zawarte w drugiej - drugim.

Niech $ r $ będzie liczbą naturalną. Zakładamy, że w przypadku $ r $ prostych można otrzymane części figury $ F $ tak pomalować dwoma kolorami, by był spełniony warunek lematu. Prowadząc $ (r + 1) $-szą prostą dzielimy płaszczyznę na dwie półpłaszczyzny. Części figury $ F $ zawarte w jednej z tych półpłaszczyzn zostawiamy tak pomalowane, jak dotychczas, a części zawarte w drugiej - malujemy odwrotnie niż dotychczas (zmieniamy kolor każdej części). Wtedy oczywiście będzie spełniony warunek lematu.

Przystępujemy do rozwiązania zadania. Ponieważ dany $ n $-kąt został podzielony za pomocą pewnej liczby prostych (przekątnych), więc części otrzymane z podziału (trójkąty) można na mocy lematu tak pomalować dwoma kolorami, by trójkąty mające wspólny bok różniły się kolorem.

Ponieważ liczba rozpatrywanych przekątnych wychodzących z dowolnego wierzchołka $ A $ danego $ n $-kąta jest parzysta, więc liczba trójkątów, dla których punkt $ A $ jest wierzchołkiem, jest nieparzysta. Wobec tego, że trójkąty te mają kolejno różne kolory, więc skrajne trójkąty mają ten sam kolor. Wynika stąd, że trójkąty, których jednym z boków jest bok danego wielokąta, są wszystkie pomalowane na ten sam kolor.

Zatem suma liczby boków $ n $-kąta i liczby wszystkich rozważanych przekątnych jest równa liczbie boków trójkątów pomalowanych tym kolorem. Liczba ta jest więc podzielna przez $ 3 $. Z drugiej strony liczba rozważanych przekątnych jest równa liczbie boków trójkątów pomalowanych drugim kolorem. Liczba ta jest więc też podzielna przez $ 3 $. Zatem różnica tych liczb, czyli liczba $ n $, tez jest podzielna przez $ 3 $.

Uwaga. Jeżeli w treści zadania trójkąty zastąpić przez $ k $-kąty, gdzie $ k > 3 $, to zastępując w powyższym rozwiązaniu trójkąty przez $ k $-kąty otrzymamy, że liczba $ n $ jest podzielna przez $ k $.

Komentarze

Dodaj nową odpowiedź