Страница 1 из 1
4 банки
Добавлено: 29 июл 2020, 13:36
Ian
Из прошлогоднего Fintech:
14. У вас есть бидон, полный молока на продажу, и 4 банки. Какого объема должны быть эти банки,
чтобы вы смогли отмерить любой объем молока от 1 до 40 литров, при том что каждая банка может
быть использована только 1 раз?
Условие как всегда у них, нестрогое, но все равно: какие 4 банки можно порекомендовать?
Видимо такие [math]a<b<c<d, что [math]k_aa+k_bb+k_cc+k_dd может принимать любое значение от 1 до 40, когда k независимо принимают значения -1,0,1. Например [math]-a-b+d=17-значит 17 литров можно набрать, наполнив банку d и отлив из нее в банки a и b
Всего значений у этой линейной комбинации [math]3^4=81.Среди них отрицательных столько же, столько и положительных, и есть 0. Вот и все 81 значения известны.Что-то не верится.
Хотя...(подожду писать)
4 банки
Добавлено: 29 июл 2020, 15:46
zykov
Ну да, степени тройки: 1, 3, 9, 27
Объем молока записываем в троичной системе. Остаток "1" - добавляем банку, остаток "2" (он же "-1") - вычитаем банку.
(40 записывается как "1111" - т.е. максимум для четырёх банок.)
4 банки
Добавлено: 29 июл 2020, 16:29
Ian
Опс, не совсем работает. Как Вы собираетесь переводить в эту квазитроичную систему (с использованием "цифр" 1.0,-1").
Я перевожу [math]V+40 в троичную и вычитаю из каждой цифры 1. Очевидно получится требуемая линейная комбинация так как 1+3+9+27=40.
А у Вас для числа V=26 что рекомендовано делать? Нужна поправка
4 банки
Добавлено: 29 июл 2020, 17:30
zykov
Алгоритм:
- Раскладываем число в троичную систему
- Для , если 0 или 1 - ничего не меняем, если 2 - заменяем на "-1", прибавляем к единицу
- Для , если 0 или 1 - ничего не меняем, если 2 или 3 - вычетаем 3, прибавляем к единицу
- Для , если 0 или 1 - ничего не меняем, если 2 или 3 - вычетаем 3, прибавляем к единицу
В результате
будут
,
(старшее ненулевое всегда
).
4 банки
Добавлено: 29 июл 2020, 17:47
Ian
да, действия соответствуют алгоритму прибавления столбиком 1111, а потом поразрядному вычитанию этого же числа)
4 банки
Добавлено: 29 июл 2020, 20:27
zykov
Тут идея простая.
При вычислениях по модулю
остаток
эквивалентен остатку
(остаток
эквивалентен остатку
и т.д.), что часто облегчает умножение или возведение в степень.
Естественно, что для того чтобы сумма не изменилась, если в одном разряде мы уменьшаем на 3, то в следующем разряде нужно увеличить на 1.
4 банки
Добавлено: 30 июл 2020, 09:02
Ian
Фактически, в первом посте уже доказана единственность решения (неупорядоченного набора банок).
Достаточно пояснить существование для каждой полезной последовательности переливаний - допустимой линейной комбинации. По условию, каждая банка использовалась 0 раз либо 1 раз. Если 1 раз - то либо то, что в нее переливалось -переливалось дополна и достанется покупателю (тогда коэффициент при банке +1), либо не дополна и без нее можно было обойтись, либо то, откуда в нее переливалось, достанется покупателю (тогда коэффициент при нашей банке -1), либо снова без переливания можно было обойтись. Поэтому условие банку использовать 1 раз (а потом долго мыть и вытирать)- и ключевое и естественное по санитарным соображениям. Реалии торговли в диких местах. Попадет пылинка в молоко оно и скиснет
4 банки
Добавлено: 11 авг 2020, 18:13
zykov
Наверно проще всего это показать таким образом.
Мы представляем нише число (количество литров) в троичной записи, но делаем это не стандартным образом. А именно, вместо цифр 0, 1, 2 мы используем цифры -1, 0, 1.
Сначала ищем остаток от нашего числа при делении на 3. Вместо остатка 2 используем эквивалентный ему остаток -1. Это даёт младшую цифру
, так что
. Далее так же выделяем следующую цифру из
и так далее.
Т.е. представляем наше число в виде
, где
из набора -1, 0, 1.