XXV OM - III - Zadanie 6

Podzielono -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 jest podzielne przez 3.

Rozwiązanie

Udowodnimy najpierw

Lemat. Jeżeli jest figurą na płaszczyźnie i za pomocą 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 . W przypadku teza jest oczywista, ponieważ prosta dzieli płaszczyznę na dwie półpłaszczyzny. Części figury zawarte w jednej półpłaszczyźnie malujemy jednym kolorem, a części zawarte w drugiej - drugim.

Niech będzie liczbą naturalną. Zakładamy, że w przypadku prostych można otrzymane części figury tak pomalować dwoma kolorami, by był spełniony warunek lematu. Prowadząc -szą prostą dzielimy płaszczyznę na dwie półpłaszczyzny. Części figury 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 -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 danego -kąta jest parzysta, więc liczba trójkątów, dla których punkt 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 -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 . 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 . Zatem różnica tych liczb, czyli liczba , tez jest podzielna przez .

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