Про трех ревнивых мужей№ 1
Valentyna

Логическая задачка.
Три ревнивых мужа и их жены должны переправиться через реку. Имеется только одна маленькая лодка, которая может выдержать одновременно только двоих. Как могут переправиться все шестеро, если никакой муж не оставит жену в присутствии других мужчин?

Личная просьба к математикам помочь решить задачку с помощью теории графов.
Профиль 

Про трех ревнивых мужей№ 2
Большой Грызь

Сначала без графов.. может можно и короче, но это - в лоб и особо не думая


       Левый берег                           Правый берег

1)М1,Ж1,М2,Ж2,М3,Ж3

                   переправляются Ж1,Ж2

2)М1,М2,М3,Ж3                                  Ж1,Ж2

                   возвращается Ж2

3)М1,М2,Ж2,М3,Ж3                               Ж1

                   переправляются Ж2,Ж3

4)М1,М2,М3                                     Ж1,Ж2,Ж3

                   возвращается Ж3

5)М1,М2,М3,Ж3                                  Ж1,Ж2

                   переправляются М1,М2

6)М3,Ж3                                        М1,Ж1,М2,Ж2

                   возвращаются М2,Ж2

7)М2,Ж2,М3,Ж3                                  М1,Ж1

                   переправляются М2,М3

8)Ж2,Ж3                                        М1,Ж1,М2,М3

                   возвращается Ж1

9) Ж1,Ж2,Ж3                                     М1,М2,М3

                   переправляются Ж2,Ж3

10) Ж1                                          М1,М2,Ж2,М3,Ж3

                   возвращается М1

11) М1,Ж1                                       М2,Ж2,М3,Ж3

                   переправляются М1,Ж1

12)                                             М1,Ж1,М2,Ж2,М3,Ж3
 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 

Про трех ревнивых мужей№ 3
Valentyna

Сложновато
А за 5 ходок?
Профиль 

Про трех ревнивых мужей№ 4
Большой Грызь

А с теорией графов.. мм.. ну, можно попробовать вот так вот..
Распишем все возможные варианты сочетаний Эм и Жо на каждом береге.
Вроде бы вот они все:

    L                      R
01) М1 М2 М3 Ж1 Ж2 Ж3 -
02) М1 М2 М3 Ж1 Ж2    - Ж3
03) М1 М2 М3 Ж1 Ж3    - Ж2
04) М1 М2 М3 Ж2 Ж3    - Ж1
05) М1 М2 М3 Ж1       - Ж2 Ж3
06) М1 М2 М3 Ж2       - Ж1 Ж3
07) М1 М2 М3 Ж3       - Ж1 Ж2
08) М1 М2 М3          - Ж1 Ж2 Ж3
09) М1 М2 Ж1 Ж2       - М1 Ж1
10) М1 М3 Ж1 Ж3       - М2 Ж2
11) М2 М3 Ж2 Ж3       - М3 Ж3

12) М1 Ж1             - М2 Ж2 М3 Ж3
13) М2 Ж2             - М1 Ж1 М3 Ж3
14) М3 Ж3             - М1 Ж1 М2 Ж2
15) Ж1 Ж2 Ж3          - М1 М2 М3
16) Ж1 Ж2             - М1 М2 М3 Ж3
17) Ж1 Ж3             - М1 М2 М3 Ж2
18) Ж2 Ж3             - М1 М2 М3 Ж1
19) Ж1                - М1 М2 М3 Ж2 Ж3
20) Ж2                - М1 М2 М3 Ж1 Ж3
21) Ж3                - М1 М2 М3 Ж1 Ж2
22)                   - М1 М2 М3 Ж1 Ж2 Ж3



Нарисуем группу узлов для левого берега - 22 узла.
Начнем с самого верхнего узла - это начальное положение (все три пары на левом берегу).
Соединим этот узел с одним из узлов, который включает в себя тех же людей, что и начальный узел минус 1-2 человека (ибо за одну перевозку могут переехать максимум два человека).
Затем этот новый узел соединим с из узлов, который включает в себя всех людей из предыдущего узла плюс 1-2 новых человека. По той же причине - обратно могут вернуться не не менее одного человека, но более 2 людей за одну перевозку.
И так далее - чередуем "минус 1-2 человека" и "плюс 1-2 человека".
У меня получалось почти без вариантов (лишь на паре этапов было несколько возможных "параллельных" вариантов).

Графически вот:

 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 

Про трех ревнивых мужей№ 5
Valentyna

Спасибо. Передам дочке.
Профиль 

Про трех ревнивых мужей№ 6
Большой Грызь

Автор: Valentyna
Дата : 02-04-06, Вск, 13:39:01

Сложновато
А за 5 ходок?


А чего сложного?

Что считать за "ходку"? Туда и обратно? Или перевозка в одну сторону - это ходка?
 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 

Про трех ревнивых мужей№ 7
Valentyna

Туда-обратно - ходка.
Профиль 

Про трех ревнивых мужей№ 8
Valentyna

Так, чтобы не сильно девушек напрягать.
Профиль 

Про трех ревнивых мужей№ 9
Большой Грызь

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

К примеру, на правом береге находится М2, а М1 находится на левом вместе с женой Ж1.
Возможен ли вариант, при котором с левого берега на правый плывёт жена Ж1, а оттуда возвращается М2?
 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 

Про трех ревнивых мужей№ 10
Valentyna

Возможен. Не криминал.
Профиль 

Про трех ревнивых мужей№ 11
Большой Грызь

Тады можно и за пять ходок
Я решал исходя из того, что запрещено и краткосрочное пересечение..
 ...everything is possible cause noone has to hide beyond the invisible...
Профиль 

Про трех ревнивых мужей№ 12
hanoch

Я знакомлюсь с Cool Folder ...
Мне очень понравилась работа МБГ и ЖВ..
Получил настоящее удовольствие .Эд (МЭ)
Профиль 

Про трех ревнивых мужей№ 13
Большой Грызь

А что такое "МБГ" и "ЖВ"?
 Only those who attempt the absurd will achieve the impossible.. (Escher)
Профиль 

Про трех ревнивых мужей№ 14
Награда

Мистер Большой Грызь , наверное
Профиль 

Про трех ревнивых мужей№ 15
Лю Ци

Аха.. А ЖВ - это я))))
 Ёрничество - это последний выход для потерявших вход
Ю. Хейфец.

Профиль 


Вы не зарегистрированы либо не вошли в портал!!!
Регистрация или вход в портал - в главном меню.



 Просмотров:   006934    Постингов:   000015