XXV OM - III - Zadanie 6

Zawody matematyczne:

XXV OM, 1973-1974

Etap:

III

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