28. Три домика, три колодца

не понял
хитро-мухлежное, это когда тропинка проходит через колодец?

Нет.
Как вы себе представляете тропинку, проходящую сквозь колодец? :)

ответ
на плоскости это невозможно, доказано топологией

Раз не возможно на плоскости
то нада построить мостики :)

А хитро-мухлёжное решение связано с зимой?

Нет, нет.
1. Мостик - это уже не тропинка.
2. Земля - плоскость?..
3. Зима тут ни при чем.

Ну если земля не плоскость
то нада прорыть подземные тунели...

если домки образуют круг, а колодца стоят во внутреней стороне круга...
... то можно сделать тропинки которые образуют двойной круг (или треугольник в круге). Долго обьяснят но решение есть!!!!!!!!!!!!!!!!!!!!!!

Sweety сделай "ОБЬЯСНЯТ"
Объясни, пожалуйста, решение , которое есть!!!!!!!!!!!!!!!!!!

Если словами объяснять долго,
можно нарисовать картинку и скинуть её на какой-нибудь публичный сервер (хоть на narod.ru и т.п.).

давай Sweety, давай
e-mail: devil_man@inbox.ru

eruditor, please...
дай правильные решения: сложно-пессимистичное, и хитро-мухлёжное. Схема Sweety не удовлетворила

Увы, но условия задачи невыполнимы - провести непересекающиеся тропинки невозможно(если, конечно, проводить на плоскости:-).

Если нельзя через колодец, то возможно тропинку стоит проложить через чужом дом. Если в нем более двух дверей - тропинки не пересекутся.

попытка выложить рисунок на ваш форум. Если не выйдет - ссылка все равно работает.
[img]http://photofile.ru/photo/lahard/2610753/large/50600371.jpg[img/]

простите, что так неакуратно нарисовал. :)

Так и есть, тропинки от 1 домика проходят через колодцы. Я это понимаю так, что тропинки, все-таки пересекаются, но точки пересечения расположены на (рядом) колодцах

В задаче не сказано КАКИМ ИМЕННО образом расположены дома и колодцы. Вот моё решение. Элементарно-очевидное с практическим подходом и оптимистическим уклоном :)

Д №1 ____Д №2____ Д №3
| / | \ |
К №1-----К №2-----К №3
\________|________/

Ээээээ! Мы так не договаривались! Куда линии отъехали?

Огромное спасибо за столь ТОЧНУЮ оценку моих скромных трудов! :)
Уточните, пожалуйста, как расположены колодцы по отношению к домам (если это существенно).

Невозможно!!!
Доказательство следующее:
у нас соединены Д1 и Д2 с колодцами К1 , К2 и К3 каждый. Тогда плоскость делится на 3 части, Внутри фигур К1 Д1 К2 Д2, К1 Д1 К3 Д3 (большой Четырехугольник, делящийся ломаной Д1 К1 Д2 На два) и пространство вне четырехугольника Д1 К2 Д2 К3. Если получилось не так в буквах, переименуйте(колодцы "равноправные"). Тогда в какой бы части не стоял дом Д3 он может быть соединен только с двумя колодцами. Ч.Т.Д.

2Zero
Расположение колодцев и домиков несущественно, и, на мой взгляд, это очевидно.

Paha
Вопрос не в том, чтобы доказать, что это невозможно (я, может быть, тоже так считаю). ГЛАВНЫЙ сказал - есть решение!(даже 2)- значит надо искать. И точка.

Zero
Доказательство отсутствия формального решения -- это тоже решение.
Но, разумеется, оно такое может быть только одно. Придумайте второе -- которое хитрое :)

А должно ли ...
хитро-мухлёжное решение быть обязательно практически реализуемым?

Что значит - реализуемым?
Всё, что могут делать жители - прокладывать тропинки.

&&&&
Я задолбался думать над этой задачей!!! Решений НЕТ и точка! Как можно смухлевать, чтобы сделать нвозможное??

Если только дом на колодце построить.

Нужно использовать вольные трактовки
тех моментов, которые в условии не оговорены.
К примеру, в условии не сказано, что семья - людей, или что находятся они на Земле.

Или, например, если сказано ...
что тропинки не должны пересекаться, то, в принципе, они могут совпадать?

Ага!!:)
так ведь дело зимой!! По тому же алгоритму прокладываем дороги, а к третьей сквозь колодцы. Считая, что уровень воды в колодцах высок (вольность формулировки) по ним можно ходить, а поскольку у других двух дороги кочаются перед колодцем, то они не пересекаются. Так?!

Гениально! Теперь давайте думать, зачем им надо целых три колодца :)
Насколько можно понять, в предыдущем варианте предлагается использовать замерзшую поверхность воды. Но, во-первых, уровень воды в колодце не бывает таким высоким. И, во-вторых, если вода замерзла, то чего ради идти к колодцу?

???
Непонятно чего они вообще из-за колодцев перегрызлись!

Ну как чего?
В одном вода холодная, во втором - горячая, ну а в третьем - питьевая, наверное...:)

Эврика!!! Есть ответ!
Все интересующиеся, вам сюда - http://www.brainbashers.com/showpuzzles.asp?page=6
PUZZLE # 27

Otvet

Otvet

Если через дом тропинку провести?
Если через дом тропинку провести то все получается

Прошу прощения, был неправ, но обещаю исправиться :)
смотреть здесь - http://threehouses-answer.narod.ru/index.html

Поразительно :-)
На самом деле, решение с планетой в виде тора, я придумал сам лет 5 назад. Неужели кто-то придумал то же самое?
Собственно, вся идея в том, что эти жители - не люди, а инопланетяне, которые живут на торообразной планете (таких пока вроде бы не обнаружено, но ничто не запрещает их существования во Вселенной).

Да, есть и другие умники ...
но живут они, по-видимому, не на просторах великой и могучей ... :(

а это вам для удобства
вот, чтобы не было разногласий, как должны стоять домикики и можно ли проводить тропинки http://www.supuzzle.com/ . решайте )

задачка решена :)
http://www.supuzzle.com/ решил это,воспользовавшись багом программы , можно провести линию через источник следующим образом: доведя линию до источника щёлкнуть правой кнопкой мыши а потом снова левой ,но уже ПОСЛЕ источника, линия пройдёт. Примечательно, что эта задача висит на главной странице. Наверное проект набирает рейтинг)

все просто
Земля - это типа шар

Могу выслать картинку
100 % решение

пришли решение 3-х домиков и 3- х колодцев

можно пожалуйста ответ на загадку 3 колодца 3 дома

Присылай!! Pavelandreevith@rambler.ru

katerina@it.kr.ua
Ребята присылайте мне тоже ответы. Пожалуйста. Paha-у тебя вообще варианты прикольные.

hunters_@inbox.ru
и мне тоже плиз )

Все что вас интересует (надо знать английский)
http://mathforum.org/dr.math/faq/faq.3utilities.html

Два варианта решения на суд eruditorа
1 Это не планета Земля и один из колодцев прокопан насквозь планеты.
2 Колодцы равностороние треугольники и расположены таким образом, что три вершины (по одной от каждого)находятся в одной точке, а сами треугольники повернуты относительно друг друга на угол 120 градусов. Тогда две тропинки идут от дома к двум соседним колодцам, а третья между этими тропинкам, между колодцами к вершине третьего колодца. Остальные тропинки аналогично.
(Эту задачу задали ребенку в 4 классе и в качестве решения я доказал, что это невозможно).

Теорема Эйлера
ТЕОРЕМА ЭЙЛЕРА

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

С именем Эйле­ра, является задача о трех домиках и трех колодцах.

Задача. Три соседа имеют три общих колодца. Можно ли провести непересека­ющиеся дорожки от каждого дома к каждому колодцу (рис. 1)?


Для решения этой задачи воспользуемся теоремой, доказанной Эйлером в 1752 году.

Теорема. Если многоугольник разбит на конечное число многоугольников так, что любые два многоугольника разбиения или не имеют общих точек, или имеют общие вершины, или имеют общие ребра, то имеет место равенство

В - Р + Г = 1, (*)

где В - общее число вершин, Р - общее число ребер, Г - число многоугольников (граней).

Доказательство. Докажем, что равенство (*) не изменится, если в каком-нибудь многоугольнике данного разбиения провести диагональ (рис. 2, а).


Действитель­но, после проведения такой диагонали в новом разбиении будет В вершин, Р+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). Каждую точку-домик соединим с каждой точкой-колодцем. Получим девять ребер, которые попарно не пересекаются.

Эти ребра образуют на плоскости многоугольник, разделенный на бо­лее мелкие многоугольники. Поэтому для этого разбиения должно выпол­няться соотношение Эйлера В - Р + Г= 1. Добавим к рассматриваемым гра­ням еще одну - внешнюю часть плоскости по отношению к многоугольнику. Тогда соотношение Эйлера примет вид В - Р + Г = 2, причем В = 6 и Р = 9. Следовательно, Г = 5. Каждая из пяти граней имеет по крайней мере четыре ребра, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро лежит ровно в двух гранях, то количество ре­бер должно быть не меньше (5∙4)/2 = 10, что противоречит условию, по которому их число равно 9. Полученное противоречие показывает, что от­вет в задаче отрицателен - нельзя провести непересекающиеся дорожки от каждого домика к каждому колодцу.
Сказал же вам Эйлер: низ-зя!!! Слушайте дядю Эйлера...И передайте главном: пщел ты...во все 3 колодца...

На самом деле не самый простой способ,через Эйлера.
Простите, не посмотрел на это решение раньше. На самом деле, это так называемая теорема Куартовского, или, если точнее, Понтрягина-куартовского, для которой эта задача является очевидным часным случаем.Дословно она гласит:"граф планарен тогда и только тогда, когда в нем нет подграфов, полученных подразбиением ребер из К2 и К3,3".
Если разбирать именно эту задачу, в неи я в конце сослался на классический факт планарных графов-Теорему Джордана.

Хотите верьте, хотите нет, но задача решена!!
Мы, на дескретной математике, как раз проходим графы и нам задали эту задачу надом... мы сказали что это невозможно, но она нам предоставила факт из книги... что 1930 году эту задачу решил какойто гений.... щас я пытаюсь найти это решение... так что не все так плохо!!!

ура
а я знаю ответ ))))) я наконецто узнал павда пол дня про маялся,чтоб понять как это все!!!!но это долгий процесс)))если что скидывайте на мыло badfx@mail.ru и я отвечу!!!

Скажете, пожалуйста, как это решается!..

простите
а в задаче указано,что тропинки должны быть прямыми?по-моему нет...и варинтов N-ое кол-во)

Ну нереально это, поймите. Если вы говорите, что решили задачу, то либо использовали 3-хмерное пространство, либо не поняли условия.

извиняюсь
дабавлю ещё.именно по условию зделать так,чтоб они не встречались(разве что непосредственно у колодца) - проще паренной репы,и ни одной пересекающейся тропинки!!!

В том то и дело, что НИКАКИХ "разве что непосредственно у колодца"! Mожно тогда и "разве что не больше 5 раз и с богатым воображением".

Земля
Вы не забывайте, что Земля круглая :) .

я в шоке
Вот это ребата вы выдаете! Ваще кул! Ток я не понял метод с тором это хитрежно мухлежный? Или нормальный?

Ну и фантазия!
Зачем что-то придумывать про тор, когда с тем же успехом можно в Земле туннели прорыть?

на плоскости сказали же вам!!
НА плоскости все!!! В крайнем случае на поверхности шара!!

ура //Ярик : (616 дн. назад)
а я знаю ответ ))))) я наконецто узнал павда пол дня про маялся,чтоб понять как это все!!!!но это долгий процесс)))если что скидывайте на мыло badfx@mail.ru и я отвечу!!!
вообщем , мне говорили условие так, На листе бумаги построить три домика и три колодца,провести к каждому по три линии, вообщем Это делается на листе Мебиуса, кому не понятно пишите на мыло) уже ответил где то более 40 людям))

и кстате писать аксиомы и доказывать их в теоремы тут не надо))) надо просто терпение и смикалка)

Ярик напиши пожал. скорее ответ, все равно не пойму как ты решил

кстати я писал тебе на badfx@mail.ru можешь ответить там:)

неужели никого ни осталось кто не знает ответа, аУУУУ!!! Вы где?

мне кажется я знаю ответ, там говорится что пересекатся тропинки не должны,но вокруг колодца есть пространство, где тропинки могут коснутся друг друга... ( место помечено *)
+ колодца, ! дома -/\ тропинки
!----
\
\ __
\-- /____________/--
/----------+ \__________*+_------------+ \
/ !--------/--------------/-------------/ \
/ /-----------------------/
-----!----------/

там опечатка...
!-------
\
\---------- /_____________
------- + \----______*+__-----------+\
/ /----------------------/-------------/ \
/ !----/ /-----------------------------------\
!------------/

не получается символами у меняч рисунок...^^^ =(
...вот...

если у кого и правда есть логический ответ ,то скиньте пожалуйста на почту...
zmv-92@mail.ru

В чистом виде, не решаемо - ни на плоскости, ни на сфере
А хитрить можно по разному. Поставить один из домов на чужую тропинку (сделав ворота в стенках). Или сделать колодец косо выступающим и одна тропинка подойдёт к косому выступу, а другая пройдёт под этим выступом. Много чего можно нахитрить...

ну и учитывая что зима, можно что-то там с закапыванием снегом придумывать, вплоть до 3-мерного лабиринта...

Это очевидно...
...Им просто следует помириться.

Помогите!!!
Киньте ктонибудь правильное решение очень срочно надо!!! zapchastivw@mail.ru

Очень нужно решение!!!
Помогите пожалуйста, очень нужно решение задачи!! tanyurova@mail.ru

Решения у этой задачи нет!!!
Что бы вы не утверждали, но на плоскости эту задачу решить нельзя...
В действительности она звучит немного по другому!
Я искала решение на многих сайтах и наконец нашла что решения нет!!!! 2 дорожки по любому пересекутся!

Вот мое решение . Земля круглая
http://i077.radikal.ru/1207/1c/37e933d53de0.jpg

Не годится
BaNaLb4iK, на той стороне "земли" линии пересекутся

Ну вы лохи, на плоскости она не решается, но в условии не сказано решить её на плоскости, дам подсказку, возьмите географическую карту земли или глобус и все ясно станет, поэтому в действительности задача имеет решение

Даже спустя много лет не могу не заметить одного маленького момента)) Вы когда отписали свой комментарий и оскорбили остальных.. Сами же написали ответ не понимая его и найдя чужое решение изменили ответ по своему неуклюжему мнению.. сразу вопрос кто лох ? те кто пытались решить или тот выскочка который нашел решение и что бы его не спалили изменил решение)??

Rostapvideo@gmail.com

Надішліть відповідь

Ребят. Всё гораздо проще, чем вы тут думаете)
Если происходит так, что 2 колодца перед домами, а один за ним. Просто подумайте. Которые за ним пересекаться не будут, а те которые спереди. Папа, не понимаю как это объяснить

это не реально ! МУЧАЮСЬ 6 ДНЕЙ!