Мельница на Компоте

[Evgeniy Sklyarevskiy]

На этой мельнице стоят 3 жернова, производительность которых отличается друг от друга. Так, на первом из них за одни сутки можно смолоть 60 четвертей зерна, на втором 54 четверти и на третьем 48 четвертей. Не было печали, но тут пришел человек, которому надо было смолоть 81 четверть зерна за как можно более короткое время на этих трех жерновах. Отсюда вопрос: «За какое наименьшее время можно смолоть зерно и сколько для этого на каждый жернов надо насыпать зерна?».

[Nadir Zaitov]

Зазача сводится к следующему:

http://latex.codecogs.com/gif.latex?max\left \{ \frac{x}{60}; \frac{y}{54};\frac{z}{48} \right \} \to min

при x + y + z = 81

Очевидно, что такой максимум достигается, если x/60, y/54, z/48 равны между собой, или имеем:

http://latex.codecogs.com/gif.latex?\left\{\begin{matrix} x+y+z=81\\ x=60t \\ y=54t \\ z=48t \end{matrix}\right.

складываем последние 3 равенства и получаем:

162t = 81

t=1/2

x= 30
y= 27
z = 24
Шухрат, получилось и уменя воспопользоваться codecogs-ом?

[Evgeniy Sklyarevskiy]

Собственно говоря задача арифметическая: сложив суточные скорости получим 162, значит все жернова должны работать по половине суток.

Но! Есть подозрение, что если часть зерна от медленного жернова передать быстрому, то время можно сократить. Но никак не могу формализовать эту мысль. Что думаете?

[JH]

Но! Есть подозрение, что если часть зерна от медленного жернова передать быстрому, то время можно сократить. Но никак не могу формализовать эту мысль. Что думаете?
Смотрите под другим углом. Медленные жернова помогают быстрому, чтобы сократить время его работы.

[Nadir Zaitov]

Но! Есть подозрение, что если часть зерна от медленного жернова передать быстрому, то время можно сократить. Но никак не могу формализовать эту мысль. Что думаете?

Ваша логика с "арифметической задачкой" подвела, ибо она дает только какое-то решение, но не доказывает его оптимальности.

Тут JH прав, ибо:
Смотрите под другим углом. Медленные жернова помогают быстрому, чтобы сократить время его работы.

Я сформулировал своей гипотезой (заявив, что это очевидно), что:

такой максимум достигается, если x/60, y/54, z/48 равны между собой

Идея в том, что если три числа разные, то за счет увеличения меньших чисели и соответствующего уменьшения больших можно максимум уменьшить и получить минимум раньше.

Т.е в целом это работает так: (идея JH) "медленные жернова нужно загрузить в помощь быстрым жерновам", но (идея ЕС) "не дольше, чем задействованы быстрые жернова". Т.е. медленные задействовать нужно, так как быстрые заняты, а если быстрые свободны - ясен пень зачем молоть на медленных? Но раз быстрые заняты, то можно молоть и на медленных в помощь.


Кстати можно было решить задачу еще сложнее и использовать для этого линейное программирование. Тогда решение получилось бы тоже, длинным путем, но тогда вообще никакой смекалки и доказательства оптимальности не нужны были бы. Кто сформулирует задачу на языке линейного программирования?