Кратчайший путь

[Утундрий]

Плагиат отсюда: http://elementy.ru/problems?questid=787

Цитата:

Четыре дома расположены в вершинах квадрата со стороной 1000 м. Можно ли соединить их дорожками так, чтобы от любого дома к любому другому можно было добраться по дорожкам (при этом не заходя в третий-лишний город - У.), а суммарная длина всех дорожек не превышала 2800 м?

Мне понравилась эта задача. Давайте её потираним?

[Руст]

Очевидно нет. Рассмотрите пути из A в C и из B в D.

[provincialka]

Руст, "очевидно" - плохое слово в математике. К сожалению, я знаю ответ к этой задаче, так что потренировать остроумие не на чем

[Утундрий]

provincialka в сообщении #845011 писал(а):

сожалению, я знаю ответ к этой задаче, так что потренировать остроумие не на чем

Можно подумать об обобщениях. Прямоугольник... Более 4 точек...

Кстати, надо будет внимательнее к паутине присмотреться: наверняка ведь реализуются такие конфигурации.

[longstreet]

Проблема Штейнера на плокости. Для вершин квадрата со стороной 1 км длина сети $2\sqrt 2$ км. Что чуть меньше, чем 2,8 км.
Для прямоугольника решение тоже известно. И, например, для точек на окружности. С общим случаем проблемы.
Хорошая книга по теме -- "Теория экстремальных сетей" (Иванов, Тужилин; 2003).

[provincialka]

longstreet в сообщении #845015 писал(а):

длина сети $2\sqrt 2$ км. Что чуть меньше, чем 2,8 км.

, ну, вообще-то $2\sqrt2 = 2\cdot1,414.. =2,828.. >2.8$

[longstreet]

Конечно, ошибся. Там должно быть $1+\sqrt{3}$. Что таки меньше.
Спасибо.

$2\sqrt2$ это просто диагонали.

[ET]

Утундрий в сообщении #845002 писал(а):

Плагиат отсюда: http://elementy.ru/problems?questid=787

Оттуда же

Цитата:

Правильный тетраэдр — это треугольная пирамида, все рёбра которой равны. Развёрткой правильного тетраэдра со стороной 10 см мы будем называть такой плоский многоугольник, из которого в результате склеивания некоторых сторон можно получить нужный тетраэдр (склейка делается не обязательно по рёбрам тетраэдра). Существует ли развёртка, периметр которой не превышает 54 см?

Почему 54?
$20 \cdot \sqrt{7}<53$

[ewert]

Утундрий в сообщении #845013 писал(а):

надо будет внимательнее к паутине присмотреться: наверняка ведь реализуются такие конфигурации.

Нет, конечно: в паутине нити обязательно пересекаются (чаще всего -- радиальные и спиральные). Иначе у них технологически не выходит. А в оптимальной сети в каждом узле сходятся не более трёх линий.

[Skeptic]

В общем случае, для любого графа с числом вершин больше 2 дорожки должны пересекаться под углом 120 градусов.

[Dimoniada]

Skeptic в сообщении #848275 писал(а):

В общем случае, для любого графа с числом вершин больше 2 дорожки должны пересекаться под углом 120 градусов.

(Оффтоп)

Так даже реальные трубопроводы прокладывают