This is a classic brainteaser. Suppose I have two water jugs of size 4 gallons and 7 gallons, and an infinite amount of water supply.
I'm allowed to fill up a gallon completely, pour water into a a jug until the jug is full, and empty the water gallons. The question asks to find a way to measure 5 gallons. There are two ways I've figured out.
- Fill and pour the 4 gallon into the 7 gallon to obtain 0/4, 4/7
- Fill and pour the 4 gallon into the 7 gallon to obtain 1/4, 7/7
- Empty the 7 gallon and pour the 1 gallon into the 7 gallon to obtain 1/7
- Fill and pour the 4 gallon into the 7 gallon to obtain 5/7
- Fill and pour the 7 gallon into the 4 gallon to obtain 4/4, 3/7
- Empty the 4 gallon and pour the 3 gallons to obtain 3/4, 0/7
- Fill the 7 gallon and pour into the 4 gallon to obtain 4/4, 6/7
- Empty the 4 gallon, then pour the 6 gallons into the 4 to obtain 4/4, 2/7
- Empty the 4 gallon and pour the 2 gallons to obtain 2/4, 0/7
- Fill the 7 gallon and pour into the 4 gallon to obtain 4/4, 5/7
My question is how to make this rigorous. How do we find explicitly all the ways to measure 5 gallons, and prove that these are the only ways to obtain 5 gallons?
Moreover, can this be generalized? Given an arbitrary number of jugs of arbitrary size, what sizes can I measure out, and how many ways are there to do so?
I suspect this may have something to do with modular arithmetic, or maybe representing this problem as a graph, but I am stuck.