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:
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.
Leave a comment
Info on how to comment
To make a comment, please send an email using the button below. Your email address won't be shared (unless you include it in the body of your comment). If you don't want your real name to be used next to your comment, please specify the name you would like to use. If you want your name to link to a particular url, include that as well.
bold, italics, and plain text are allowed in
comments. A reasonable subset of markdown is supported, including lists,
links, and fenced code blocks. In addition, math can be formatted using
$(inline math)$ or $$(your display equation)$$.
Please use plaintext email when commenting. See Plaintext Email and Comments on this site for more. Note also that comments are expected to be open, considerate, and respectful.
Comments (2)
2011-03-22 davidlowryduda
It turns out that this is related to a set of problems called the 'Decanting Problems' and the 'Three Jug Problem.'
In general, the decanting problem relates to the smallest amount that can be isolated from a set of containers and is easily solved by considering the gcd. I will write about it in another post.
The three jug problem is more complicated. With three jugs of a given size and given starting amounts, the task is to measure out a certain amount of water using the standard pours.
2011-03-23 davidlowryduda
It also seems that the first question, as written, is not very interesting. As long as one chooses bottles of vastly different sizes, one can guarantee the largest possible for any finite amount of pours.
Instead, it would be more interesting to maximize the largest connected interval of results, e.g. maybe one can get results 11, 12, 13, 14, 15, 16, and 17 - yielding an interval of size 7. So I instead ask,
What sets $ S$ maximize $ |{bf F}(S;p)|_c$, where $ |cdot|_c$ denotes the largest connected interval of results?