№19 Задачи на переливание профиль

Задачи на переливания, или
Алгоритм перебора всех случаев

В последнем сборнике для подготовки к ЕГЭ [1] появилась новая задача 19 на переливания. Поскольку переливаниями я занимался, делая книгу «Задачи на смекалку» для 5-6 классов (в соавторстве с И.Ф. Шарыгиным), то мне показалось интересным придумать алгоритм решения таких задач, исключающий пропуск вариантов, повторные переливания и циклы. Не хотелось бы, чтобы учащиеся на экзамене занимались переливанием «из пустого в порожнее». Начнём с подготовительной задачи.

ЗАДАЧА 1. Имеется три ведра объёмом 2 л, 4 л и 6 л. В двух первых их которых налита вода до верха, а третье ведро пустое. За одно переливание можно перелить воду из одного ведра в другое. Переливание заканчивается в тот момент, когда или первое ведро опустеет, или второе ведро заполнится (на вёдрах нет делений). Выливать воду из вёдер (не в ведро) или брать воду из какого-либо источника запрещается.

а) Можно ли через несколько переливаний разлить воду в три ведра поровну?

б) Укажите все возможные способы наполнения вёдер.

в) Можно ли через несколько переливаний разлить воду в два ведра поровну?

Решение. Результаты переливаний будем записывать в виде троек чисел. Исходное состояние описывается тройкой чисел 240, что означает 2 л в 1-м ведре (двухлитровом), 4 литра во 2-м ведре (четырёхлитровом), 0 л в 3-м ведре (шестилитровом). Каждое переливание проводим по следующему алгоритму, пропуская невозможные шаги:

1) из 1-го во 2-й; 2) из 1-го во 3-й;    

3) из 2-го во 1-й; 4) из 2-го во 3-й;   

5) из 3-го во 1-й;    6) из 3-го во 2-й.

Алгоритм завершается после n-го шага, если после него не получено ни одного нового варианта переливания.

Результаты переливания запишем в таблицу.

Первое переливание даёт лишь два способа наполнения вёдер: 042 и 204.

Второе переливание даёт лишь три новых способа наполнения вёдер, повторы вариантов заполнения с полученными ранее — в таблице они в строках выше или в той же строке слева — зачёркнуты.

Третье переливание не даёт ни одного нового способа наполнения вёдер, на этом алгоритм завершён.

Теперь ответим на вопросы задачи.

а) Разлить воду в три ведра поровну можно. Вариант переливаний:

240 – 042 – 222.

б) Все возможные способы наполнения вёдер есть в таблице, выпишем их: 240, 042, 204, 222, 006, 024.

в) Разлить воду в два ведра поровну нельзя, так как варианты 033, 303, 330 получить невозможно. Есть и второе объяснение. Так как объёмы вёдер выражены чётными числами, то в результате любого переливания из исходных чётных чисел сложением или вычитанием невозможно получить нечётное число.

ОТВЕТ: а) да: 240 – 042 – 222; б) 240, 042, 204, 222, 006, 024; в) нет.

ЗАДАЧА 2. Имеется три ведра объёмом 2 л, 4 л и 5 л. В двух первых их которых налита вода до верха, а третье ведро пустое. За одно переливание можно перелить воду из одного ведра в другое. Переливание заканчивается в тот момент, когда или первое ведро опустеет, или второе ведро заполнится. Выливать воду из вёдер или брать воду из какого-либо источника запрещается.

а) Можно ли через несколько переливаний разлить воду в три ведра поровну?

б) Можно ли через несколько переливаний разлить воду в два ведра поровну?

Решение. Применим описанный выше алгоритм переливаний для трёх вёдер, результаты переливаний запишем в таблицу.

а) После двух переливаний 240 – 042 – 222 получаем ответ на вопрос задачи: да.

б) Выполнив четыре переливания 240 – 042 – 015 – 213 – 033, получаем ответ на вопрос задачи: да.

ОТВЕТ: а) да: 240 – 042 – 222; б) да: 240 – 042 – 015 –213 – 033.

ЗАДАЧА 3. У Бори нет источника воды, но есть три ведра различных объёмов, в двух их которых есть вода. За один шаг Боря переливает воду из ведра, в котором она есть, в другое ведро. Переливание заканчивается в тот момент, когда или первое ведро опустеет, или второе ведро заполнится. Выливать воду из ведер запрещается.

а) Мог ли Боря через несколько шагов получить в одном из вёдер ровно 2 л воды, если сначала у него были ведра объёмами 4 л и 7 л, полные воды, а также пустое ведро объёмом 8 л?

б) Мог ли Боря через несколько шагов получить равные объёмы воды во всех ведрах, если сначала у него были ведра объёмами 5 л и 7 л, полные воды, а также пустое ведро объёмом 10 л?

в) Сначала у Боря были ведра объёмами 3 л и 6 л, полные воды, а также пустое ведро объёмом n л. Какое наибольшее натуральное значение может принимать n, если известно, что как бы ни старался Боря, он не сможет получить через несколько шагов ровно 4 л воды в одном из вёдер? [1]

Решение. а) Применим описанный выше алгоритм переливаний для трёх вёдер, результаты переливаний запишем в таблицу.

Получить 2 л воды в одном ведре можно, выполнив пять переливаний 470 – 407 – 047 – 443 – 173 – 128, или шесть переливаний 470 – 407 – 308 – 371 – 461 – 065 – 425. Завершать алгоритм нет необходимости, так как ответ на вопрос уже получен. Ответ на вопрос: да.

В сборнике [1] ответ приведён для семи переливаний: 470 – 074 – 038 – 308 – 371 – 461 – 065 – 425. Как видим, следование предложенному алгоритму позволяет получить тот же результат за меньшее число шагов.

б) У Бори было 12 л воды, получить в трёх вёдрах по 4 л воды он не мог, так как такой результат нельзя получить в соответствии с условиями задачи. Каждый результат переливания должен давать хотя бы одно пустое или одно полное ведро, а этого нет в результате 444. Ответ на вопрос: нет.

в) Выполним алгоритм переливаний для n = 9.

Получить 4 л воды в одном ведре невозможно, так как алгоритм переливаний завершен и 4 л не появилось ни в одном ведре. Кроме того, переливая объёмы, кратные 3, в вёдра, объёмы которых кратны 3, мы складываем и вычитаем числа, кратные 3, поэтому получить 4 л невозможно.

Если взять n 9, то алгоритм переливаний полностью повторится, так как в третье ведро входит вся вода для любого n ≥ 9 и в третье ведро невозможно налить более 9 л. Это означает, что для любого натурального
n ≥ 9 Боря не сможет получить через несколько шагов ровно 4 л воды в одном из вёдер. Наибольшего натурального значения n не существует.

А в сборнике [1] приведён ответ: n = 8.

Давайте выполним алгоритм переливаний для n = 8.

Получить 4 л воды в одном ведре можно за четыре переливания:

360 – 063 – 018 – 315 – 045.

Ответ на вопрос: наибольшее значение n = 8.

ОТВЕТ: а) да: 470 – 407 – 047 – 443 – 173 – 128; б) нет; в) наибольшего натурального значения n не существует.

===========Задания для самостоятельного решения============

ЗАДАЧА 4. Имеется три ведра объёмом 3 л, 4 л и 6 л. В двух первых их которых налита вода до верха, а третье ведро пустое. За одно переливание можно перелить воду из одного ведра в другое. Переливание заканчивается в тот момент, когда или первое ведро опустеет, или второе ведро заполнится (на вёдрах нет делений). Выливать воду из вёдер или брать воду из какого-либо источника запрещается. За какое наименьшее число переливаний можно получить в одном из вёдер:

а) 1 л воды; б) 2 л воды; в) 5 л воды?

ОТВЕТ: а) за 2 переливания; б) за 3 переливания; в) за 5 переливаний: 340 – 304 – 106 – 142 – 322 – 025.

ЗАДАЧА 5. У Вити нет источника воды, но есть три ведра различных объёмов, в двух их которых есть вода. За один шаг Боря переливает воду из ведра, в котором она есть, в другое ведро. Переливание заканчивается в тот момент, когда или первое ведро опустеет, или второе ведро заполнится. Выливать воду из ведер запрещается.

а) Мог ли Витя через несколько шагов получить в одном из вёдер ровно 5 л воды, если сначала у него были ведра объёмами 3 л и 6 л, полные воды, а также пустое ведро объёмом 7 л?

б) Мог ли Витя через несколько шагов получить равные объёмы воды во всех вёдрах, если сначала у него были ведра объёмами 6 л и 9 л, полные воды, а также пустое ведро объёмом 7 л?

в) Сначала у Вити были ведра объёмами 2 л и 4 л, полные воды, а также пустое ведро объёмом n л. Найдите наибольшее натуральное значение n, при котором он сможет получить через несколько шагов ровно 3 л воды в одном из вёдер?

ОТВЕТ: а) да; б) нет; в) 5.

======================================================

Литература

1. ЕГЭ 2019 : Математика. Профильный уровень. 36 вариантов. Типовые тестовые задания от разработчиков ЕГЭ и 800 заданий части 2 / под ред. И.В. Ященко. М.: Издательство «Экзамен», издательство МЦНМО, 2019. – 239 с.

P.S. Выражаю благодарность за помощь в редактировании материала П.М. Камаеву.

А.В. Шевкин, [email protected]