Explorations in math and programming
David Lowry-Duda

In a previous post I considered the following two 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$?

I then changed the first question, which I think is perhaps not so interesting, to the following:

What sets $S$ maximize $|{\bf F}(S;p)|_c$, where $|\cdot|_c$ denotes the largest connected interval of results?

Let's explore a few cases to see what these answers might look like.

One Bottle

With only one bottle, the game is simple. The bottle is either full or empty, and so there is little to explore. Clearly, any bottle will maximize $ |{\bf F}|_c$ and choosing a bottle of size 1 will maximize $ \lfloor {\bf F} \rfloor$, at 2.

Two Bottles

With two bottles, the game already becomes interesting. If we restrict ourselves to only 1 pour, then we would want a 1-bottle and a 2-bottle so that $ \lfloor {\bf F} \rfloor = 3.$ But say we have 2 pours with which to work - it might seem like a good idea to stay with the 1-bottle and the 2-bottle, as we could fill them both so that $ \lfloor {\bf F}(1, 2; 2) \rfloor = 4,$ but this is not optimal. Instead, consider a 1-bottle and a 3-bottle. We could fill the 1-bottle or we could fill the 3-bottle with our first pour. With a full 3-bottle, would could pour it into the 1-bottle to get 2 liters left in the 3-bottle. Or we can fill both bottles, getting 4 liters. So we know that $ \lfloor {\bf F} (S;2) \rfloor \geq 5.$

Is that the maximum? How might we know. I claim that yes, 5 is the maximum for 2 bottles and 2 pours. How might we see this? Suppose that we have one a-bottle and one b-bottle, and that b > a. Then with our first pour, we can either fill the a-bottle or fill the b-bottle. With our second pour, we might fill the other bottle, or we might pour one bottle into the other. In other words, we can get the amounts a, b, a+b, and b-a (by pouring the b-bottle into the a-bottle, yielding a full a-bottle and the amount b-a in the b-bottle). Note that pouring the a-bottle into the b-bottle doesn't accomplish anything in this case. As these are all the possibilities, at most 4 amounts can be made. Thus 5 is, in fact, the maximum.

One might ask, is this the unique set that guarantees 4 consecutive amounts that can be filled? Yes, and here's a sketch of why. If the smaller number is 3 or greater, then when it's added to the larger number a gap of more than 4 emerges. So the smaller number is 1 or 2. But then the larger number can't be larger than 4. Then there are only a few possibilities left.

Let's look at one more case for 2 bottles as further evidence of what an interesting set of questions we have. With three pours, the possible amounts are a, b, a + b, b-a, and a + a (gotten from filling the a-bottle, pouring it into the b-bottle, and filling the a-bottle again). Upon a little consideration, we see that one 2-bottle and one 3-bottle gives the resulting amounts 1, 2, 3, 4, and 5 - the maximal set.

I haven't yet looked into other bottle amounts that yield 5 consecutive results, nor into the cases where there are more pours.

Actually, on second thought, the case for four or more pours is very easy. The thing is that the only way for the additional pours to matter is if the b-bottle is large enough to hold many multiples of the a-bottle. But in this case, the only way that consecutive amounts can be achieved is if the smaller amount is 1. Thus for any odd number of pours 2n+1 = p and large bottle of size n, one can get all amounts from 1 to p+1 in at most p pours. But as my first post demonstrated, this is also perhaps not optimal.

I might think about this later.

Three Bottles

For three bottles, the game quickly becomes more complicated. For 1 pour, of course, it's trivial and the set 1, 2, 3 maximizes $ \lfloor {\bf F} \rfloor$ at 4.

For 2 pours, it seems that the sets (1, 3, 6) and (2, 4, 5) both maximize $ \lfloor {\bf F} \rfloor$ at 8, but neither are optimal. With bottles of size a, b, and c, with c > b > a, the possibilities are a, b, c, a+b, a+c, b+c, c-a, c-b, and b-a. In this sense, we could hope for 9 consecutive amounts. Is it possible?

3 pours presents interesting opportunities, but I haven't looked into them fully, either.

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.

Comment via email

Comments (2)
  1. 2011-03-27 Guy

    Have you worked more on the problem?

  2. 2011-03-28 davidlowryduda

    I'm still in the write-lots-of-examples stage. Nothing yet to report.