59
Головоломки и графы
М.П. Барболин
Всем известны задачи на разливание, переправы; дележи. Они прочно вошли в практику математических кружков, Викторин, математических вечеров и т. д. Объчно такие задачи решаются «в уме» и требуют немалого остроумия и смекалки. Найти решение такой задачи каким-либо одним способом бывают не сложно. Гораздо сложнее указаать самый короткий способ или все возможные способы решения.
Ответы на эти вопросы можно легко получить с помощью графических схем, состоящих из точек, соединенных между собой стрелками. Такие схемы называются графами.
Задача 1. Два целевка имеются полный кувшин молока в 8 литров, а также два пустых кувшина в 5 и 3 литра. Как они могут разделить молоко поровну?
Для решения задачи воспользовемся графами. Присвоим каждому кувшину номер: кувшину в 8 л — № 1, кувшину в 5 л — № 2, кувшину в 3 л — № 3. Рассмотрим возможные варианты наполнения кувшинов, получающейся в результате одного переливания.
В начальной момент кувшин № 1 наполнен, а № 2 и № 3 — пустые.
Изображим это состояние точкой (8.0.0.) (рис. 1). Теперь из кувшина № 1 можно перелить в кувшин № 2 пять литров или в кувшин № 3 — три литра. В результате получается два новых варианта наполнения кувшинов (3.5.0.) и (5.0.3.). Их также изобразим точками, а стрелками показем, что они получаются из исходного варианта (8.0.0.) (рис. 2). Других вариантов одним переливанием получить нельзя.
Делаем второе переливание. Чтобы не пропустить ни одной возможности, рассмотрим кувшины в порядке номеров. Берем вариант (3.5.0.) (в кувшине № 1 — 3 литра, в кувшине № 2 — 5 литров, кувшин № 3 — пуст). Из кувшина № 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). Кувшин с номером три пустой, поэтому его можно не рассматривать.
Далее переходим к варианту (5.0.3.). Рассуждая аналогично предыдущему, получим еще один варианта
60
(5.3.0.) и соответственно достижим граф.
Теперь ясно, что процесс решения свойится к «выращиванию» граф-дерева. Продолжая рассуждения, doitем до графа, изобразенного на рисунке 4.
На нем видны две цепи, идущие из точки (8.0.0.) и заканчивающейся искомым вариантом (4.4.0.). Они соответствуют двум различным способам
Рис. 1
(8.0.0.)
(3.5.0.) (5.0.3.)
Рис. 2.
(8.0.0.)
(3.5.0.) (5.0.3.)
(0.5.3.) (3.2.3.) (5.3.0.)
Рис. 3.
(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.)
искомого разливания:
I способ: (8.0.0.) → (3.5.0.) → (3.2.3.) → (6.2.0.)→ (6.0.2.)→ (1.5.2.)→ (1.4.3.)→ (4.4.0.).
II способ: (8.0.0.) → (5.0.3.) → (5.3.0.)→ (2.3.3.)→ (2.5.1.)→ (7.0.1.)→ (7.1.0.)→ (4.1.3.)→ (4.4.0.)
Задача 2. Перевозчики (П) нужно переправить через реку волка (В), козу (К) и мешок с капустой (М). Лодка так мала, что кроме перевозчика можно взять только один из объектов. Кроме того, капусту нельзя оставлять вместе с козу, а козу — вместе с волком. Как осуществить переправу?
Пусть для определения в начальной момент все находятся на левом берегу (Л. Б.). Изображим исходную ситуацию точкой и обозначим ее так: (В. К. М. П. || —) (рис. 5). В первыйрейс перевозчик может взять только козу (так как ее нельзя оставить ни с волком, ни с капустой). В результате получим новую situацию: (В. М. || К. П.). (волк и мешок на левом берегу, коза и перевозчик — на правом). Изображим ее точкой и проведем к ней стрел-
Рис. 5.