Помогите решить задачу

МIX:
Пересекаясь с фигурой, вы заканчиваете прямую, так что увы.

Но уже близко, явно где-то не хватает штриха

Sci:
Держите :)

Linux:
Было :).

Sci:
А что конкретно сказано в условии задачи? Если там так и написано - круг, квадрат, то этот вариант вполне подходит, так как круг и квадрат - это плоскости.

Linux:
Я имел ввиду, что первый её решил :).

Эта задачка про три домика и три колодца:
Есть три домика в деревне. Живет там три семьи. И есть и них три колодца. Однажды (зимой) эти семьи из-за них перессорились и, так как колодцы общие, решили проложить от каждого домика к каждому колодцу по тропинке. Но так как поссорились они сильно, не хотят они, чтобы тропинки пересекались.
Задача: соединить каждый из 3-х домиков с каждым из 3-х колодцев тропинками (их 9) так, чтобы они не пересекались.


ТЕОРЕМА ЭЙЛЕРА

В 2007 году исполнится 300 лет со дня рождения Леонарда Эйлера – одного из величайших математиков, работы которого оказа*ли решающее влияние на развитие многих современных разделов математи*ки. Л. Эйлер был действительным членом Петербургской Академии наук, оказал большое влияние на развитие отечественной математической школы и в деле подготовки кадров ученых-математиков и педагогов в России. Поражает своими размерами научное наследие ученого. При жизни им опуб*ликовано 530 книг и статей, а сейчас их известно уже более 800. Причем последние 12 лет своей жизни Эйлер тяжело болел, ослеп и, несмотря на тяжелый недуг, продолжал работать и творить. Статистические подсчеты показывают, что Эйлер в среднем делал одно открытие в неделю. Трудно найти математическую проблему, которая не была бы затронута в произве*дениях Эйлера. Все математики последующих поколений так или иначе учи*лись у Эйлера, и недаром известный французский ученый П.С. Лаплас ска*зал: "Читайте Эйлера, он – учитель всех нас".

С именем Эйле*ра, является задача о трех домиках и трех колодцах.
Задача. Три соседа имеют три общих колодца. Можно ли провести непересека*ющиеся дорожки от каждого дома к каждому колодцу.


Для решения этой задачи воспользуемся теоремой, доказанной Эйлером в 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. Полученное противоречие показывает, что от*вет в задаче отрицателен - нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу.

Никак получается, из любопытства полезла в яндекс, и вот что нашлось.