Кто знает, как ответить? Думаю над решением целый месяц : (

Question

Задача, похожая на задачу Эйлера: три дома напротив трёх колодцев, от каждого дома три дорожки к каждому колодцу, чтобы они не пересекались, вобще есть несколько решений и надо, чтобы все пути были как можно короче. Не нашла ни одного решения, кто поможет?

Answer 1

Много неясностей . Эти дома могут быть хатично стоящие, треугольником, в линию и ещё как разно. ЯСНО, ЧТО ПУТИ БУДУТ РАЗЛИЧНЫМИ, К КАЖДОМУ КОЛОДЦУ .
Просто отводите их от разных сторон домов.

Answer 2

Теорема имет непросредственное отношение к теории графов. 1. заключается в рассмотрении трех вариантов, остающихся после проведения 8ми тропинок. Решение: Обозначим вершины графа А, B, C, 1, 2, 3 сответственно трем домикам и колодцам формулировки задачи, и докажем, что девятую дорогу - ребро графа, не пересекающюю другие ребра, провести невозможно. Проведенные в графе ребра А-1, А-2, A-3 и В-1, В-2, В-З (сответствующие дорожкам от домиков А и В ко всем трем колодцам) . Построенный таким образом граф разделил рабочую плоскость на 3 области: X, У, Z. Вершина B, в зависимости от е расположения на плоскости, попадает в одну из таких 3х областей. Если рассмотреть каждый из 3х случаев «попадания» вершины B в одну из областей X, Y, Z - то увидите, что всякий раз какая-нибудь одна из вершин графа 1, 2 или 3 (или один из колодцев "соседей") получится недоступной для построения дороги от вершины B (т. е. невозможно будет построить одно из ребер B1, B2 или B3. которое не пересекло бы уже имеющиеся в графе ребра) . Сответственно - ответ - нельзя! 2. основываясь на сотношении того же Эйлера для многоугольников Решение: Предположим, что эти 9 тропинок можно проложить. Обозначим домики точками H1, H2, H3, колодцы - точками C1, C2, C3. Каждую точку-дом соединим с каждой точкой-колодцем. Получились ребра (графа) в количестве девяти штук, которые попарно не пересекаются. Такие ребра образуют на рассматриваемой плоскости задачи многоугольник, поделенный на меньшие многоугольники. Для такого разбиения должно выполняться известное сотношение Эйлера B - P + G = 1. Добавляем к рассматриваемым граням еще одну - внешнюю часть плоскости относительно рассматриваемомого многоугольника. Тогда сотношение Эйлера примет вид B - P + G = 2, причем B = 6 и P = 9. Получается, G = 5. Каждая из пяти граней имет по крайней мере четыре ребра, так как, по условию задачи Эйлера, ни одна из дорожек не должна напрямую соединять два колодца или два дома. Так как любое ребро лежит ровно в 2х гранях, то кол-во ребер графа должно быть не меньше 5*4/2 = 10. Это противоречит условию исходной задачи, по которому их число равно девять! Полученное противоречие доказывает, что ответ в задаче о 3х колодцах Эйлера отрицателен. Решение получается при переходе в трехмерное пространство, либо при вспоминании того факта, что Земля - круглая, либо "замараживании" высокого уровня воды в одном из колодцев и предположения что по льду можно ходить, либо при "строительстве" мостов, туннелей и т. п. .