XXXII - II - Zadanie 5

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.
om32_2r_img_12.jpg

Komentarze

Dodaj nową odpowiedź