XXXV OM - I - Zadanie 10

Zawody matematyczne:

XXXV OM, 1983-1984

Etap:

Na płaszczyźnie dane jest $3n$ punktów, wśród których nie ma trzech punktów współliniowych. Dowieść, że istnieje $n$ rozłącznych trójkątów o wierzchołkach w danych punktach.

Rozwiązanie

Rozważmy wszystkie proste, z których każda przechodzi przez dwa punkty danego zbioru $3n$ punktów. Prostych tych jest skończenie wiele, więc istnieje prosta $l$ , która nie jest prostopadła do żadnej z nich. Zrzutujmy wszystkie dane punkty prostopadle na prostą $l$ , rzuty żadnych dwóch punktów nie pokrywają się. Ponumerujmy dane punkty $A_1, \ldots, A_{3n}$ zgodnie z kolejnością, w jakiej ich rzuty są usytuowane na prostej $l$ . Trójkąty $A_{3i-2} A_{3i-1} A_{3i}$ dla $i = 1,\ldots, n$ są rozłączne.