XXXII - II - Zadanie 5

Zawody matematyczne:

XXXII OM, 1980-1981

Etap:

Na płaszczyźnie dane są dwa zbiory rozłączne $A$ i $B$ , z których każdy składa się z $n$ punktów, przy czym żadne trzy punkty zbioru $A \cup B$ nie leżą na jednej prostej. Udowodnić, że istnieje zbiór $n$ rozłącznych odcinków domkniętych, z których każdy ma jeden koniec w zbiorze $A$ , drugi zaś w zbiorze $B$ .

Rozwiązanie

Dla każdego różnowartościowego przyporządkowania punktów $B_j$ zbioru $B$ punktom $A_i$ zbioru $A$ możemy obliczyć sumę odległości wyznaczonych przez to przyporządkowanie par punktów $(A_i, B_j)$ . Przypuśćmy, że przyporządkowując punktowi $A_i$ punkt $B_i$ dla $i = 1,2,\ldots,n$ otrzymujemy minimalną wartość tej sumy. Wówczas odcinki $\overline{A_iB_i}$ nie mają punktów wspólnych (rys. 12), bo gdyby $C$ był punktem wspólnym odcinków $\overline{A_iB_i}$ i $\overline{A_jB_j}$ dla $i \ne j$ , to wobec różnowartościowości przyporządkowania $C$ nie jest końcem żadnego z tych odcinków i w trójkątach $A_iB_jC$ oraz $A_jB_iC$ byłoby $A_iB_j < < A_iC+B_jC$ oraz $A_jB_i < A_jC+B_iC$ , więc $A_iB_j+ A_jB_i < A_iC + CB_i + B_jC + CA_j$ , a zatem $A_iB_j+A_jB_i < A_iB_i+A_jB_j$ , co jest sprzeczne z założeniem o minimalnej sumie odległości.