Супер загадка.
-
так они не как не пересикутся вода же под землей ведется газ на землей а свет по проводам
-
по мне так легко0)
-
Вот сука дибилы. Ваши ебучие блядо ответы типа "ответа нет" не принимаются. Вот проведёте все линии (от дома к дому нельзя) (и с пробелами нельзя) вот тогда и дам голоса.
Ответ я не знаю потому что мне её так же загадали и если я отвечу я получу 100.000 рублей. 100 голосов с этой суммы это мало. -
Вот в 3D сделать это было-бы просто, но вот в 2D это невозможно
Первый
еще раз это невозможно
Для решения этой задачи воспользуемся теоремой, доказанной Эйлером в 1752 году.
Теорема. Если многоугольник разбит на конечное число многоугольников так, что любые два многоугольника разбиения или не имеют общих точек, или имеют общие вершины, или имеют общие ребра, то имеет место равенство
В - Р + Г = 1, (*)
где В - общее число вершин, Р - общее число ребер, Г - число многоугольников (граней).
Доказательство. Докажем, что равенство (*) не изменится, если в каком-нибудь многоугольнике данного разбиения провести диагональ
Действитель но, после проведения такой диагонали в новом разбиении будет В вершин, Р+1 ребер и количество многоугольников увеличится на единицу. Следовательно, имеем
В - (Р + 1) + (Г+1) = В – Р + Г.
Пользуясь этим свойством, проведем диагонали, разбивающие входя щие многоугольники на треугольники, и для полученного разбиения пока жем выполнимость соотношения (*) (рис. 2, б). Для этого будем последо вательно убирать внешние ребра, уменьшая количество треугольников. При этом возможны два случая:
а) для удаления треугольника ABC требуется снять два ребра, в на шем случае AB и BC;
б) для удаления треугольника MKN требуется снять одно ребро, в нашем случае MN.
В обоих случаях равенство (*) не изменится. Например, в первом случае после удаления треугольника граф будет состоять из В-1 вершин, Р-2 ребер и Г-1 многоугольника:
(В - 1) - (Р + 2) + (Г -1) = В – Р + Г.
Самостоятельно рассмотрите второй случай.
Таким образом, удаление одного треугольника не меняет равенства (). Продолжая этот процесс удаления треугольников, в конце концов мы придем к разбиению, состоящему из одного треугольника. Для такого раз биения В = 3, Р = 3, Г = 1 и, следовательно, B - Р + Г= 1. Значит, равенство () имеет место и для исходного разбиения, откуда оконча тельно получаем, что для данного разбиения многоугольника справедливо соотношение (*).
Заметим, что соотношение Эйлера не зависит от формы многоугольников. Многоугольники можно деформировать, увеличивать, уменьшать или даже искривлять их стороны, лишь бы при этом не происходило разрывов сторон. Соотношение Эйлера при этом не изменится.
Приступим теперь к решению задачи о трех домиках и трех колодцах.
Решение. Предположим, что это можно сделать. Отметим домики точками Д1, Д2, Д3, а колодцы - точками К1, К2, К3. Каждую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются.
Эти ребра образуют на плоскости многоугольник, разделенный на более мелкие многоугольники. Поэтому для этого разбиения должно выполняться соотношение Эйлера В - Р + Г= 1. Добавим к рассматриваемым гра ням еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид В - Р + Г = 2, причем В = 6 и Р = 9. Следовательно, Г = 5. Каждая из пяти граней имеет по крайней мере четыре ребра, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ребер должно быть не меньше (5*4)/2 = 10, что противоречит условию, по которому их число равно 9. Полученное противоречие показывает, что ответ в задаче отрицателен - нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу.
-
-
Решение с помощью теоремы Эйлера.
Предположим, что граф G — плоский, то есть существует его плоское представление. Граф G — связный, он не имеет ни одного моста, поэтому не имеет и перегородок. По формуле Эйлера, V – E + R = 2. Здесь V — число вершин, E — число ребер, R — число граней с учетом бесконечной грани. Подсчитаем число вершин и ребер: V = 6, E = 9, поэтому R = 2 – 6 + 9 = 5.
Теперь оценим удвоенное число ребер 2E. Заметим, что в графе нет простых циклов длиной 3, то есть граница любой грани в плоском представлении графа G содержит не менее четырех ребер. Заметим, что каждое ребро служит границей двух граней, так как мы учитываем и бесконечную грань. При этом число 4R не может быть больше удвоенного числа всех ребер: 4R ≤ 2E. Если бы мы знали число ребер в границе каждой грани, то их сумма должна быть равна 2E; но известно, что 2E = 18, а 4R = 20, откуда 20 ≤ 18. Полученное противоречие доказывает, что предположение было неверное, то есть граф G — не плоский.
