Punkty i odcinki

[mol_ksiazkowy]

Danych jest \(\displaystyle{ 2n}\) różnych punktów na płaszczyźnie. Udowodnić że są one końcami wzajemnie rozłącznych \(\displaystyle{ n}\) odcinków.

[szw1710]

Na szybko: pokazałbym, że można tak wprowadzić układ współrzędnych, że odcięte wszystkich punktów są wzajemnie różne. To zakończy dowód. Możliwość wyboru takiego układu (kierunku na płaszczyźnie) jest prosta do uzasadnienia.

[Dasio11]

Inaczej: rozważmy takie połączenie tych \(\displaystyle{ 2n}\) punktów w pary, które łączymy odcinkiem, aby suma długości tych odcinków była najkrótsza. Wtedy te odcinki są parami rozłączne: załóżmy przeciwnie, że pewne dwa odcinki się przecinają, i rozważmy czwórkę punktów złożoną z końców tych odcinków. W oparciu o nierówność trójkąta łatwo wykazać, że dowolna zmiana parowania dla tej czwórki spowoduje, że suma długości odcinków zmaleje, co prowadzi do sprzeczności.