Головоломки и графы
методическая разработка по теме

ГОЛОВОЛОМКИ И ГРАФЫ.

Всем известны задачи на переливание, переправы, дележи. Найти решение такой задачи каким-либо одним способом бывает несложно. Гораздо сложнее указать самый короткий способ или рассмотреть все возможные варианты.

        Ответы на эти вопросы можно легко получить с помощью графических схем, состоящих из точек, соединенных между собой стрелками. Такие схемы называются графами.

        Задача №1. Два человека имеют полный кувшин молока в 8 литров, а также два пустых кувшина в 5 и в 3 литра. Как они смогут разделить молоко поровну?

        Для решения задачи воспользуемся графами. Присвоим каждому кувшину номер: кувшину в 8 л - №1, кувшину в 5 л - №2, кувшину в 3 л - №3. Рассмотрим возможные варианты наполнения кувшинов, получающиеся в результате одного переливания.

        В начальный момент кувшин №1 наполнен, а №2 и №3 – пустые. Изобразим это состояние точкой (8.0.0) (рис.1)                         (8.0.0)

                                                                (рис.1)

Теперь из кувшина №1 можно перелить 5 литров в кувшин №2 или в кувшин №3 – 3 литра. В результате получаются два новых варианта наполнения кувшинов (3.5.0) и (5.0.3). Их тоже изобразим точками, а стрелками покажем, что они получаются из исходного варианта (8.0.0) (рис.2). Других вариантов одним переливанием получить нельзя.

Делаем второе переливание. Чтобы не пропустить ни одно возможности, рассмотрим кувшины в порядке номеров. Берем вариант (3.5.0). Из кувшина №1 можно перелить молоко только в №3, в результате получится новый вариант наполнения (0.5.3). На графе от точки (3.5.0) ведем стрелку к точке (0.5.3) (рис. 3). Из кувшина №2 можно перелить в №1 и №3 (переливание в два кувшина считается как два последовательных переливания!), но переливание в кувшин №1 не дает нового варианта (получающийся при этом вариант (8.0.0) уже рассматривался), поэтому делать такое переливание нецелесообразно. Переливая молоко из №2 в №3, получаем новый вариант (3.2.3), показываем это на графе точкой (3.2.3) (рис.3). Кувшин №3 пустой, поэтому его можно не рассматривать.

Теперь ясно, что процесс решения сводится к «выращиванию» графа-дерева. Продолжая рассуждения, дойдем до графа, изображенного на рис. 4.

                                               (8.0.0)    

           (3.5.0)                                                                                       (5.0.3)

(0.5.3)                      (3.2.3)                                                                            (5.3.0)

                                 (6.2.0)                                                                             (2.3.3)  

                                 (6.0.2)                                                                             (2.5.1)

                                 (1.5.2)                                                                             (7.0.1)              

                                 (1.4.3)                                                                              (7.1.0)

                                 (4.4.0)                                                                              (4.1.3)

                                                                       (рис.4)                                       (4.4.0)

На нем видны две цепи, идущие из точки (8.0.0) и заканчивающиеся искомым вариантом (4.4.0). Они соответствуют двум различным способам искомого разливания:

I способ:

II способ: .

Задача №2. Перевозчику (П) нужно переправить через реку волка (В), козу (К) и мешок с капустой (М). Лодка так мала, что можно взять только один из объектов. Кроме того, капусту нельзя оставлять вместе с козой, а козу – вместе с волком. Как осуществить переправу?

Пусть для определенности в начальный момент все находятся на левом берегу (Л.Б.). Изобразим исходную ситуацию точкой и обозначим ее так: (В.К.М.П.) (рис.5). В первый рейс перевозчик может взять только козу (так как ее нельзя оставить ни с волком, ни с капустой). В результате получим новую ситуацию: (В.М.К.П.) (волк и мешок на левом берегу, перевозчик и коза – на правом). Изобразим ее точкой и проведем к ней стрелку из точки (В.К.М.П.), показывающую, что она получена из ситуации  (В.К.М.П.) за одну перевозку. Обратно перевозчик едет один (возвращаться к исходной ситуации – везти козу обратно – нецелесообразно). Возникающую ситуацию (В.М.П.К) изображаем точкой на графе. Далее перевозчик имеет две возможности: везти или волка (В), или мешок (М). Получаем две возможные ситуации: (В.П.М.К) или (М.П.В.К). Каждую из них изображаем точкой на графе. Рассматривая аналогично каждый из полученных вариантов, мы придем к требуемой ситуации: (П.К.В.М) (рис.5). Две (частично совпадающие) цепи на графе соответствуют двум различным способам решения задачи.

                                                                    (В.К.М.П.)

                                                                     (В.М.К.П)

                                                                    (В.М.ПК)

(В.П.М.К.)                                                                                           (М.П.В.К)

(В.П.К.М)                                                                                            (П.К.М.В)

(К.П.В.М)

(П.К.В.М)

(П.К.В.М)                                      (рис.5)

Упражнения.

1. Задача Пуассона. Известному французскому математику Симону Пуассону (1781-1810) в юности предложили задачу. Заинтересовавшись ею, Пуассон увлекся математикой и посвятил этой науке всю свою жизнь. Вот эта задача.

Некто имеет 12 пинт вина (пинта – мера объема) и хочет подарить из этого количества половину, но у него нет сосуда в 6 пинт. У него два сосуда: один в 8 пинт, другой в 5 пинт. Каким образом налить 6 пинт вина в сосуд на 8 пинт? Какое наименьшее число переливаний необходимо при этом сделать?

2. Имеется 4 бочки.  В первую входит 24 ведра, емкость второй – 13 ведер, третьей – 11 ведер, четвертой – 5 ведер. В начале наполнена только первая бочка. Требуется ее содержимое разлить на три равные части так, чтобы первые три бочки содержали по 8 бедер, а четвертая осталась пустой.
3. (Старинная задача). Три солдата и три разбойника должны переправиться через реку. Они нашли лодку, в которую помещаются только два человека. Нельзя оставить на берегу больше разбойников, чем солдат. Как им всем шестерым переправиться через реку? Найти все возможные способы.*)

*) Разрешается оставлять на берегу одних разбойников или одних солдат.