Monday, September 25, 2017

mathematics - A general solution to the decanting problem? (aka jug-pouring, water-pouring)


Take a look at these two questions:
- A Set of Water Jug Challenges
- Pouring problem


Now I'm asking for a generalised solution to that problem.


I define the problem as follows:





  • You are required to measure exactly $n$ litres of water.




  • You have $j$ jugs.




  • Each jug has volume $v_m$ where $m$ is the jug-number ($1$ to $j$).





  • You have an infinitely large tub of water.




  • There is no indication on the jugs saying how much liquid is in them, and you can't judge it by eye. You do know for sure when they are empty and when they are full.




Question(s):




  • For what sets of values ($n$, $j$, $v_1$ to $v_j$) is this solvable?





  • For cases which are solvable, what algorithm can be used to find the solution?




This is intended to be a math/algorithm problem, rather than a lateral thinking problem, so 'creative' solutions such as "I use the infinitely-large tub of water to solve the world's drought problems, am elected world president for my services to humanity, and keep the jugs as a souvenir" may be upvoted if they're witty/entertaining but won't be marked as correct.


NB: Searching the entire possible space of jug-pouring actions is clearly a solution. But it isn't a very interesting or elegant one.


See also:





No comments:

Post a Comment

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...