Точки на плоскости

*

Сложность: 

На плоскости дано 2n точек. Докажите, что их можно попарно соединить так, чтобы отрезки не пересекались.

Подсказка

В выпуклом четырёхугольнике сумма длин диагоналей всегда больше суммы длин двух противоположных сторон.

Решение

Рассмотрим все возможные варианты соединения точек n отрезками и выберем из них тот, для которого сумма длин отрезков минимальна. Если в нём какие-то два отрезка AB и CD пересекаются, то, заменив их на пару AC, BD, получим набор отрезков меньшей длины, что противоречит выбору минимального набора.




Добавить комментарий

Plain text

  • Запрещены тэги HTML.
  • Адреса страниц и электронной почты автоматически преобразуются в ссылки.
  • Строки и параграфы переносятся автоматически.
Type the characters you see in this picture. (verify using audio)
Type the characters you see in the picture above; if you can't read them, submit the form and a new image will be generated. Not case sensitive.