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 $latex S$ and for a number of pours $latex p$, define

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

For example, we saw above that $latex {\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 $latex 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 $latex \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 $latex S $ maximize $latex |{\bf F}(S;p)| $ for various $latex p$?

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

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

Pingback: Containers of Water II « mixedmath

Pingback: Perfect Partitions « mixedmath