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

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’ll return to 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.

More than three bottles?

The options are interesting. I am now convinced this is an interesting problem. In forthcoming posts, I will discuss the decanting problem and the three jug problem.

Advertisements