Задача про импортозамещение

Итак, сельское хозяйство расцветает. В связи с этим местные власти принимают решение немного поддержать фермера, торгующего молоком. Ему говорят: 

“Нам известно, что ты продаешь до 40 литров коровьего молока за раз. Вот тебе немного денег, купи на них 4 любые банки, чтобы с их помощью точно отмерять любой объем от 1 до 40 литров (в зависимости от заказа покупателя). Но не забывай про санитарные требования: молоко можно наливать в каждую банку только по одному разу, переливать — негигиенично. Т.е. при обслуживании покупателя каждую банку можно использовать только единожды. Затем все емкости нужно мыть и пользоваться ими снова со следующим покупателем по тому же принципу. Учти этот момент при выборе мерных банок”.

Вопрос: какие банки нужно приобрести фермеру, чтобы с их помощью отмерять любой объем молока в диапазоне 1-40 литров, используя каждую тару не больше 1 раза?

Решение

Банка №1

Минимальный необходимый для нас объем — это один литр. Без лишних раздумий приобретаем эту банку и идем дальше.

Банка №2

К первой таре добавим вторую, но так, чтобы получить от нее максимум пользы. Для этого разница между ее объемом и объемом первой должна быть наибольшей. Проверим по очереди последующие: на два, три и четыре литра.

2-х литровая.

Если дать фермеру и ее, то он сможет отмерять один литр (банка №1), два литра (банка №2) и три литра (две банки вместе). Негусто.

3-х литровая.

В этом случае фермер отмерит один литр (банка №1), два литра (из 3-х литровой перелить литр в первую), три литра (банка №3) и четыре литра (сумма двух банок). Так уже лучше.

4-х литровая.

Эта емкость вместе с первой не дает возможности отмерить два литра. Поэтому она фермеру не подходит. Значит, останавливаем свой выбор на 3-х литровой.

Банка №3

Мы уже поняли, как с помощью двух банок отмерять 1-4 литра. Чтобы получить 5, придется использовать и третью емкость.

По логике, которой мы пользовались раньше, нам снова нужна как можно большая по объему тара. Это значит, что нужно выбрать ее так, чтобы пять литров у нас получалось при выливании из банки №3 четырех литров. Почему именно четырех? Потому что это наибольший объем, который возможно измерить банками №1 и №2.

Вычислим объем банки №3: 4+5=9.

Теперь нужно выяснить, сколько литров фермер сможет отмерить этими емкостями:

Прекрасно! Банка №3 на 9 литров нас устраивает.

Банка №4

Мы подошли к 14-ти литрам. Используем ту же логику, что в предыдущих случаях, и найдем самую большую банку, которой можно отмерить 13 л, чтобы остаток равнялся 14-ти: 13+14=27.

Делаем проверку:

Сходится! Это значит, что четвертая банка фермера должна вмещать в себя 27 литров молока.

Ответ

Фермеру нужно приобрести банки объемом 1, 3, 9 и 27 литров.