Consider the old middle-school type puzzle question: Can you measure 6 quarts of water using only a 4 quart bottle and a 9 quart bottle? Yes, you can, if you’re witty. Fill the 9 quart bottle. Then fill the 4 quart bottle from the 9 quart bottle, leaving 5 quarts in the 9-bottle. Empty the 4-bottle, and fill it again from the 9-bottle, leaving only 1 quart in the 9-bottle.  Again empty the 4-bottle, and pour the 1 quart from the 9-bottle into it. Now fill the 9-bottle one last time and pour into the 4-bottle until it’s full – at this time, the 4-bottle has 4 quarts and the 9 bottle has 6 quarts. Aha!

But consider the slightly broader question: how many values can you get? We see we can get 1, 4, 5, 6, and 9 already. We can clearly get 8 by filling the 4-bottle twice and pouring this bottle into the 9. With this, we could get 4 by filling the 4-bottle again and then pouring as much as possible into the 9-bottle when its filled with 8 – as this leaves 3 quarts in the 4-bottle. Finally, we can get 2 by taking 6 quarts and trying to pour it into an empty 4-bottle. (With 2, we get 7 by putting the 2 into the 4-bottle and then trying to pour a full 9-bottle into the 4-bottle). So we can get all numbers from 1 to 9. If we were really picky, we could note that we can then easily extend this to getting all numbers from 0 to 13 quarts, albeit not all in one container.

If you go through these, it turns out it is possible to get any number between 0 and 13 quarts with a 4-bottle and a 9-bottle in at most 10 pours, where a pour includes filling a bottle from the water source (presumably infinite), pouring from one bottle into another, or emptying the water into the water source. Now I propose the following question:

Given only 2 bottles (of an integer size) and up to 10 pours, what is the largest N s.t. we can measure out 0, … , N quarts (inclusive)?

As is natural, let’s extend this a bit further. For any subset of the natural numbers S and for a number of pours p, define

{\bf F}(S; p) := the set R of possible results after using at most p pours from containers of sizes in S

For example, we saw above that {\bf F}(4,9;10) = (0,1, ... , 13). But is this maximal for two containers and 10 pours? If we only allow 5 pours, the set R reduces to size 7; and if we consider the smallest result not attainable, we get 2 quarts. That is very small! I’m tempted to use \lfloor {\bf F} \rfloor to denote the smallest unattainable positive integer amount, but that’s only a whim.

Ultimately, this leads to two broad, open (as far as I know) questions:

Questions
What sets S maximize |{\bf F}(S;p)| for various p?
What sets S maximize \lfloor {\bf F}(S; p) \rfloor for various p?

Perhaps these have already been explored? I don’t even know what they might be called.

Advertisements