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