4 банки

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

4 банки

Сообщение Ian » 29 июл 2020, 13:36

Из прошлогоднего Fintech:
14. У вас есть бидон, полный молока на продажу, и 4 банки. Какого объема должны быть эти банки,
чтобы вы смогли отмерить любой объем молока от 1 до 40 литров, при том что каждая банка может
быть использована только 1 раз?
Условие как всегда у них, нестрогое, но все равно: какие 4 банки можно порекомендовать?
Видимо такие [math], что [math] может принимать любое значение от 1 до 40, когда k независимо принимают значения -1,0,1. Например [math]-значит 17 литров можно набрать, наполнив банку d и отлив из нее в банки a и b
Всего значений у этой линейной комбинации [math]81.Среди них отрицательных столько же, столько и положительных, и есть 0. Вот и все 81 значения известны.Что-то не верится.
Хотя...(подожду писать)

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

4 банки

Сообщение zykov » 29 июл 2020, 15:46

Ну да, степени тройки: 1, 3, 9, 27
Объем молока записываем в троичной системе. Остаток "1" - добавляем банку, остаток "2" (он же "-1") - вычитаем банку.
(40 записывается как "1111" - т.е. максимум для четырёх банок.)

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

4 банки

Сообщение Ian » 29 июл 2020, 16:29

Опс, не совсем работает. Как Вы собираетесь переводить в эту квазитроичную систему (с использованием "цифр" 1.0,-1").
Я перевожу [math] в троичную и вычитаю из каждой цифры 1. Очевидно получится требуемая линейная комбинация так как 1+3+9+27=40.
А у Вас для числа V=26 что рекомендовано делать? Нужна поправка

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

4 банки

Сообщение zykov » 29 июл 2020, 17:30

Алгоритм:
  1. Раскладываем число в троичную систему $a_3 27 + a_2 9 + a_1 3 +a_0$
  2. Для $a_0$, если 0 или 1 - ничего не меняем, если 2 - заменяем на "-1", прибавляем к $a_1$ единицу
  3. Для $a_1$, если 0 или 1 - ничего не меняем, если 2 или 3 - вычетаем 3, прибавляем к $a_2$ единицу
  4. Для $a_2$, если 0 или 1 - ничего не меняем, если 2 или 3 - вычетаем 3, прибавляем к $a_3$ единицу
В результате $a_i$ будут $0$, $\pm 1$ (старшее ненулевое всегда $+1$).

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

4 банки

Сообщение Ian » 29 июл 2020, 17:47

да, действия соответствуют алгоритму прибавления столбиком 1111, а потом поразрядному вычитанию этого же числа)

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

4 банки

Сообщение zykov » 29 июл 2020, 20:27

Тут идея простая.
При вычислениях по модулю $p$ остаток $p-1$ эквивалентен остатку $-1$ (остаток $p-2$ эквивалентен остатку $-2$ и т.д.), что часто облегчает умножение или возведение в степень.
Естественно, что для того чтобы сумма не изменилась, если в одном разряде мы уменьшаем на 3, то в следующем разряде нужно увеличить на 1.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

4 банки

Сообщение Ian » 30 июл 2020, 09:02

Фактически, в первом посте уже доказана единственность решения (неупорядоченного набора банок).
Достаточно пояснить существование для каждой полезной последовательности переливаний - допустимой линейной комбинации. По условию, каждая банка использовалась 0 раз либо 1 раз. Если 1 раз - то либо то, что в нее переливалось -переливалось дополна и достанется покупателю (тогда коэффициент при банке +1), либо не дополна и без нее можно было обойтись, либо то, откуда в нее переливалось, достанется покупателю (тогда коэффициент при нашей банке -1), либо снова без переливания можно было обойтись. Поэтому условие банку использовать 1 раз (а потом долго мыть и вытирать)- и ключевое и естественное по санитарным соображениям. Реалии торговли в диких местах. Попадет пылинка в молоко оно и скиснет

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

4 банки

Сообщение zykov » 11 авг 2020, 18:13

zykov писал(а):Source of the post Тут идея простая.

Наверно проще всего это показать таким образом.
Мы представляем нише число (количество литров) в троичной записи, но делаем это не стандартным образом. А именно, вместо цифр 0, 1, 2 мы используем цифры -1, 0, 1.
Сначала ищем остаток от нашего числа при делении на 3. Вместо остатка 2 используем эквивалентный ему остаток -1. Это даёт младшую цифру $d_0$, так что $x=3 x_1 + d_0$. Далее так же выделяем следующую цифру из $x_1$ и так далее.
Т.е. представляем наше число в виде $x=d_3 3^3 + d_2 3^2 + d_1 3^1 + d_0 3^0$, где $d_i$ из набора -1, 0, 1.


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 6 гостей