Условие
Имеются два пустых сосуда вместимостью 7 л и 4 л и кран с водой. За одно действие можно наполнить любой сосуд доверху из крана, вылить всю воду из любого сосуда или переливать воду из одного сосуда в другой, пока первый не опустеет или второй не наполнится. Какое наименьшее число действий нужно, чтобы в одном из сосудов оказалось ровно 5 л воды?
Подсказка
Записывайте количество воды в сосудах парой чисел и следите, какие действия не возвращают назад.
Сравните две стратегии: наполнять всё время большой сосуд или всё время малый.
Показать ответ
8
Пошаговое решение
- Записываем состояния
Состояние будем записывать парой (x; y): x литров в 7-литровом сосуде и y литров в 4-литровом. Вначале (0; 0), цель — чтобы x или y равнялось 5.
- Понимаем, какие ходы имеют смысл
Первым действием можно только наполнить один из сосудов: выливать и переливать пока нечего. Дальше выливать воду, которую только что набрали, или переливать её обратно бессмысленно — это возвращает к уже бывшему состоянию и лишь удлиняет путь. Поэтому остаются две цепочки: всё время наполнять большой сосуд и переливать из него в малый (опорожняя малый) или наоборот.
- Идём по цепочке, начиная с 4-литрового сосуда
1) наполняем 4-литровый — (0; 4); 2) переливаем из 4-литрового в 7-литровый — (4; 0); 3) наполняем 4-литровый — (4; 4); 4) переливаем из 4-литрового в 7-литровый — (7; 1); 5) выливаем 7-литровый — (0; 1); 6) переливаем из 4-литрового в 7-литровый — (1; 0); 7) наполняем 4-литровый — (1; 4); 8) переливаем из 4-литрового в 7-литровый — (5; 0). Цель достигнута за 8 действий.
- Сравниваем с цепочкой от 7-литрового сосуда
Другая цепочка: (7; 0) → (3; 4) → (3; 0) → (0; 3) → (7; 3) → (6; 4) → (6; 0) → (2; 4) → (2; 0) → (0; 2) → (7; 2) → (5; 4). В ней 5 л появляется только после 12-го действия, это дольше.
- Делаем вывод
Любая кратчайшая последовательность действий — начало одной из двух цепочек, а раньше чем за 8 действий нужный объём не появляется ни в одной из них. Значит, наименьшее число действий 8.
Ответ: 8