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