Сельское хозяйство на подъёме, и власти решили поддержать фермера из Вологды, который торгует молоком. Они сказали ему: «Мы знаем, что тебе нужно продавать до 40 л молока за раз, поэтому вот тебе деньги, купи любые четыре банки, чтобы ты мог ими точно отмерять 40 л или меньше, смотря сколько нужно покупателю».
Фермер обрадовался, но тут пришёл Роспотребнадзор и сказал: «Больше одного раза молоко в банку наливать и переливать нельзя, это негигиенично. Учитывай это при выборе тары». То есть при каждой продаже одному покупателю каждую банку допустимо использовать только один раз. Потом ёмкости можно мыть и применять заново с новым покупателем.
Вопрос. Какого объёма банки нужно купить фермеру, чтобы иметь возможность отмерить ими от 1 до 40 л, используя любую из них только по одному разу?
Первая банка
Самый маленький объём, который нам нужен — 1 л. Сразу купим эту банку и посмотрим, приведёт ли это нас к верному решению.
Вторая банка
Теперь мы с первой ёмкостью можем отмерять 1 л, но не более. Надо добавить вторую банку и использовать её по максимуму. Это значит, что разница в объёме между первой и второй ёмкостями должна быть как можно больше. Проверим банки на 2, 3 и 4 л.
- Двухлитровая. С её помощью мы можем отмерить 1 л (первой банкой), 2 л (второй банкой) и 3 л (сумма первой и второй, обозначим как 1 + 2). Негусто.
- Трёхлитровая. Теперь мы отмеряем 1 л (первая банка), 2 л (наливаем 3 л в большую банку, сливаем литр в маленькую), 3 л (вторая банка) и 4 л (3 + 1). Уже лучше.
- Четырёхлитровая. С ней мы не сможем отмерить 2 л. Значит, эта банка нам не подходит и вторая ёмкость будет на 3 л.
Вывод: второй мы покупаем трёхлитровую банку.
Третья банка
Мы уже умеем отмерять 4 л двумя банками, а 5 л будем наливать уже тремя.
Раз нам нужна тара как можно больше, нужно сделать так, чтобы 5 л у нас получилось, когда мы из третьей банки заберём 4 л. Это максимальный объём, который мы можем из неё взять первыми двумя ёмкостями. Найдём объём третьей банки:
4 + 5 = 9 (литров)
Проверим, сколько литров можем отмерить этими тремя банками:
5 л = 9 − 3 − 1 (отливаем всё из третьей в первые две)
6 л = 9 − 3
7 л = 9 − 3 + 1
8 л = 9 − 1
9 л = 9 (третья банка)
10 = 9 + 1
11 = 9 + 3 − 1
12 = 9 + 3
13 = 9 + 3 + 1 (наполняем все три банки)
Отлично, значит, третья банка на 9 л нам подходит.
Четвёртая банка
Мы остановились на 13 л, и нужно перейти к 14 л. Снова применим ту же тактику и поищем наибольшую банку, из которой можно забрать 13 л, чтобы осталось 14:
13 + 14 = 27 (литров)
Проверим эту банку:
14 = 27 − 9 − 3 − 1 (отливаем всё в первые три)
15 = 27 − 9 − 3
16 = 27 − 9 − 3 + 1
17 = 27 − 9 − 1
18 = 27 − 9 (отливаем в третью)
19 = 27 − 9 + 1
20 = 27 − 9 + 3 − 1
21 = 27 − 9 + 3
22 = 27 − 9 + 3 + 1
23 = 27 − 3 − 1
24 = 27 − 3 (отливаем во вторую)
25 = 27 − 3 + 1
26 = 27 − 1 (отливаем в первую)
27 = 27 (четвёртая банка)
28 = 27 + 1 (четвёртая и первая)
29 = 27 + 3 − 1
30 = 27 + 3 (четвёртая и вторая)
31 = 27 + 3 + 1
32 = 27 + 9 − 3 − 1
33 = 27 + 9 − 3
34 = 27 + 9 − 3 + 1
35 = 27 + 9 − 1
36 = 27 + 9 (четвёртая и третья)
37 = 27 + 9 + 1
38 = 27 + 9 + 3 − 1
39 = 27 + 9 + 3
40 = 27 + 9 + 3 + 1 (заполняем все четыре банки)
Всё сошлось, и нам подходит четвёртая ёмкость на 27 л.
Ответ
Нам нужно купить банки на 1, 3, 9 и 27 л.
