XXXII - I - Zadanie 9

Zawody matematyczne:

XXXII OM, 1980-1981

Etap:

W przestrzeni dany jest zbiór $3n$ punktów, z których żadne cztery nie leżą na jednej płaszczyźnie. Udowodnić, że zbiór ten można rozbić na $n$ takich zbiorów trójelementowych $\{A_i, B_i, C_i\}$ , że trójkąty $A_iB_iC_i$ są parami rozłączne.

Rozwiązanie

Dowód indukcyjny. Dla $n = 1$ teza twierdzenia jest oczywiście spełniona. Załóżmy, że teza jest spełniona dla pewnego $n$ i rozpatrzmy $3(n+1)$ punktów w przestrzeni, z których żadne cztery nie leżą na jednej płaszczyźnie. Najmniejszy zbiór wypukły zawierający rozważane punkty jest wielościanem, którego każda ściana jest trójkątem (bo żadne cztery punkty nie leżą w jednej płaszczyźnie). Niech $A$ , $B$ , $C$ będą wierzchołkami jednego z tych trójkątów. Zbiór pozostałych $3n$ punktów można na mocy założenia indukcyjnego rozbić na $n$ zbiorów $\{A_1, B_1, C_1\}$ o tej własności, że trójkąty $A_iB_iC_i$ są parami rozłączne. Ponieważ wszystkie punkty $A_1,B_1 C_1$ leżą po jednej stronie płaszczyzny $ABC$ , więc trójkąt $ABC$ jest rozłączny z każdym z trójkątów $A_iB_iC_i$ . Otrzymaliśmy więc podział zbioru $3(n+1)$ punktów na podzbiory trójelementowe o wymaganej własności.

Na mocy zasady indukcji teza twierdzenia jest spełniona dla każdej liczby naturalnej $n$ .