Олимпиады · 5–6 классыЛогика и перебор

Олимпиада, 5–6 класс: переливания — как отмерить воду

Два и три сосуда без делений: кратчайшая цепочка переливаний или доказательство, что нужное количество отмерить нельзя.

Вариант № 15510

Олимпиада, 5–6 класс: переливания — как отмерить воду · Вариант № 15510 · Школьный тур · Имя: ____________________

1
Есть два сосуда: на 6 л и на 11 л, без делений, и кран с неограниченным запасом воды. За один ход можно: наполнить сосуд из крана, вылить его целиком или перелить воду из одного сосуда в другой (до тех пор, пока источник не опустеет или приёмник не наполнится). За какое наименьшее число ходов можно получить ровно 8 л воды в одном из сосудов? Если это невозможно, ответьте 0.
Ответ: 14
Следим за состоянием $(x,y)$ — сколько воды в первом и втором сосудах. Кратчайший путь (найден перебором всех состояний):
1. наполнить первый сосуд из крана: $(0,0)\to(6,0)$ .
2. перелить из первого во второй: $(6,0)\to(0,6)$ .
3. наполнить первый сосуд из крана: $(0,6)\to(6,6)$ .
4. перелить из первого во второй: $(6,6)\to(1,11)$ .
5. вылить второй сосуд: $(1,11)\to(1,0)$ .
6. перелить из первого во второй: $(1,0)\to(0,1)$ .
7. наполнить первый сосуд из крана: $(0,1)\to(6,1)$ .
8. перелить из первого во второй: $(6,1)\to(0,7)$ .
9. наполнить первый сосуд из крана: $(0,7)\to(6,7)$ .
10. перелить из первого во второй: $(6,7)\to(2,11)$ .
11. вылить второй сосуд: $(2,11)\to(2,0)$ .
12. перелить из первого во второй: $(2,0)\to(0,2)$ .
13. наполнить первый сосуд из крана: $(0,2)\to(6,2)$ .
14. перелить из первого во второй: $(6,2)\to(0,8)$ .
Всего ходов: $14$ .
2
Три сосуда вместимостью 8, 5, 3 л. Первый полон воды, остальные пусты. Воду переливают только так: из одного сосуда в другой до тех пор, пока источник не опустеет или приёмник не наполнится до краёв (на глаз отмерять нельзя). За какое наименьшее число переливаний можно получить по 4 л в двух сосудах? Если невозможно, ответьте 0.
Ответ: 7
Состояния записываем тройками $(a,b,c)$ — сколько воды в каждом сосуде; вначале $(8,0,0)$ .
1. перелить из первого в второй (до границы): $(8,0,0)\to(3,5,0)$ .
2. перелить из второго в третий (до границы): $(3,5,0)\to(3,2,3)$ .
3. перелить из третьего в первый (до границы): $(3,2,3)\to(6,2,0)$ .
4. перелить из второго в третий (до границы): $(6,2,0)\to(6,0,2)$ .
5. перелить из первого в второй (до границы): $(6,0,2)\to(1,5,2)$ .
6. перелить из второго в третий (до границы): $(1,5,2)\to(1,4,3)$ .
7. перелить из третьего в первый (до границы): $(1,4,3)\to(4,4,0)$ .
Всего переливаний: $7$ . Меньшим числом не получится — это показывает поиск по всем состояниям (их конечное число).
3
Есть два сосуда: на 3 л и на 8 л, без делений, и кран с неограниченным запасом воды. За один ход можно: наполнить сосуд из крана, вылить его целиком или перелить воду из одного сосуда в другой (до тех пор, пока источник не опустеет или приёмник не наполнится). За какое наименьшее число ходов можно получить ровно 4 л воды в одном из сосудов? Если это невозможно, ответьте 0.
Ответ: 10
Следим за состоянием $(x,y)$ — сколько воды в первом и втором сосудах. Кратчайший путь (найден перебором всех состояний):
1. наполнить первый сосуд из крана: $(0,0)\to(3,0)$ .
2. перелить из первого во второй: $(3,0)\to(0,3)$ .
3. наполнить первый сосуд из крана: $(0,3)\to(3,3)$ .
4. перелить из первого во второй: $(3,3)\to(0,6)$ .
5. наполнить первый сосуд из крана: $(0,6)\to(3,6)$ .
6. перелить из первого во второй: $(3,6)\to(1,8)$ .
7. вылить второй сосуд: $(1,8)\to(1,0)$ .
8. перелить из первого во второй: $(1,0)\to(0,1)$ .
9. наполнить первый сосуд из крана: $(0,1)\to(3,1)$ .
10. перелить из первого во второй: $(3,1)\to(0,4)$ .
Всего ходов: $10$ .
4
Есть два сосуда: на 6 л и на 11 л, без делений, и кран с неограниченным запасом воды. За один ход можно: наполнить сосуд из крана, вылить его целиком или перелить воду из одного сосуда в другой (до тех пор, пока источник не опустеет или приёмник не наполнится). За какое наименьшее число ходов можно получить ровно 2 л воды в одном из сосудов? Если это невозможно, ответьте 0.
Ответ: 10
Следим за состоянием $(x,y)$ — сколько воды в первом и втором сосудах. Кратчайший путь (найден перебором всех состояний):
1. наполнить первый сосуд из крана: $(0,0)\to(6,0)$ .
2. перелить из первого во второй: $(6,0)\to(0,6)$ .
3. наполнить первый сосуд из крана: $(0,6)\to(6,6)$ .
4. перелить из первого во второй: $(6,6)\to(1,11)$ .
5. вылить второй сосуд: $(1,11)\to(1,0)$ .
6. перелить из первого во второй: $(1,0)\to(0,1)$ .
7. наполнить первый сосуд из крана: $(0,1)\to(6,1)$ .
8. перелить из первого во второй: $(6,1)\to(0,7)$ .
9. наполнить первый сосуд из крана: $(0,7)\to(6,7)$ .
10. перелить из первого во второй: $(6,7)\to(2,11)$ .
Всего ходов: $10$ .
5
Есть два сосуда: на 3 л и на 8 л, без делений, и кран с неограниченным запасом воды. За один ход можно: наполнить сосуд из крана, вылить его целиком или перелить воду из одного сосуда в другой (до тех пор, пока источник не опустеет или приёмник не наполнится). За какое наименьшее число ходов можно получить ровно 1 л воды в одном из сосудов? Если это невозможно, ответьте 0.
Ответ: 6
Следим за состоянием $(x,y)$ — сколько воды в первом и втором сосудах. Кратчайший путь (найден перебором всех состояний):
1. наполнить первый сосуд из крана: $(0,0)\to(3,0)$ .
2. перелить из первого во второй: $(3,0)\to(0,3)$ .
3. наполнить первый сосуд из крана: $(0,3)\to(3,3)$ .
4. перелить из первого во второй: $(3,3)\to(0,6)$ .
5. наполнить первый сосуд из крана: $(0,6)\to(3,6)$ .
6. перелить из первого во второй: $(3,6)\to(1,8)$ .
Всего ходов: $6$ .

Коротко о теме

Записывай состояния как пары (тройки) чисел и перебирай ходы — число состояний конечно.
С сосудами $a$ и $b$ можно получить лишь количества, кратные $\text{НОД}(a,b)$ и не большие $\max(a,b)$ .
Идти обратно от результата иногда проще: какое состояние предшествует нужному?
Уровни: «Разминка» — тренировочная задача на одну идею, «Обычный» — задача школьного тура, «Challenge» — уровень регионального этапа (идеи нужно соединять).

Уровни: Тренировочная · Школьный тур · Региональный этап. Все ответы вычислены программой из тех же чисел, что и условие.

Ещё тренажёры

Раздел «Логика и перебор»

Другие темы: 5 класс