12
$\begingroup$

You know those , where you have two jugs of different sizes, and a water fountain, and you need to get a specific amount of water into one of the jugs using the smallest number of transfers? I came up with a decanting problem like that, but then it turned out that there were two solutions tied for "smallest number of transfers".

In those solutions, how full did the larger jug end up?

CLARIFICATION: In problems of this sort, it doesn't matter which jug ends up containing the target volume.

$\endgroup$
  • $\begingroup$ "I came up with a decanting problem like that," Please share. $\endgroup$ – ABcDexter Nov 24 '17 at 19:27
  • 2
    $\begingroup$ @ABcDexter Well, that would be something of a spoiler, wouldn't it? The good news is, once someone posts the answer to this puzzle, you'll be able to as well. $\endgroup$ – Sneftel Nov 24 '17 at 19:32
  • $\begingroup$ Well, to answer your question, "how full did the larger jug end up" Exactly what was asked in the question. say 3L an 5L jug, and we need 4L, we would get 4L in the 5L jug in say n steps. A simple way is : to BFS the solution to check if it's possible and optimal. $\endgroup$ – ABcDexter Nov 24 '17 at 19:36
  • 1
    $\begingroup$ I'm not sure what you're getting at. I'm not asking anything about graph search algorithms. I'm just asking how full the larger jug was. You don't need any additional information. $\endgroup$ – Sneftel Nov 24 '17 at 19:40
  • 1
    $\begingroup$ We're getting into spoiler territory here, but note that I did not ask "what is the final volume of water the larger jug contains". Give it some more thought, try to come up with some examples, see if you can detect a pattern. $\endgroup$ – Sneftel Nov 24 '17 at 19:48
3
$\begingroup$

For two solutions to be equally fast

a kind of symmetry is required. More precisely the empty part of the big jug must be symmetric to the filled part. In other words, the big jug will end up half full.

Explanation:

The big jug (volume $V$) can start either with $0$ or $V$ filling, which is already symmetric around $\frac{V}{2}$. In the first step one can transfer the volume of the small jug $v$ in or out of the big one, so its filling after the first transfer is either $v$ or $V-v$, which again has the same distance to the final filling.
In the next step one could either revert the previous one (which doesn't bring you closer to the required filling) or again withdraw or add a volume of $v$ to the big jug – unless the volume would exceed $[0, V]$. In the second case the big jug has now a filling of $V$ or $0$ and the small one of $2v - V$ or $V - v$, respectively. Again, one can see that the symmetry between around the fillings $\frac{V}{2}$ and $\frac{v}{2}$ are maintained.
Also in all further steps this symmetry can not be broken, because for every transfer there is an opposite operation on the "mirror image", that instead of pouring $n$ liters from jug A to jug B pours it the other way round.

Two symmetric paths leading to the same solution in the same number of transfers requires the two paths to meet. This is exactly the case in the symmetry axis, i.e. when the big jug is half full.

Example:


One can clearly see the symmetry showing as the amount of air in the left path being equal to the amount of water in the right path.

$\endgroup$
  • $\begingroup$ That's a great way to explain it. Well done! $\endgroup$ – Sneftel Dec 2 '17 at 9:27
2
$\begingroup$

My second thought is that:

The larger jug will always be half full.

While I don't have a formal proof, I think that:

If there are two optimal solutions, then the goal must be to get half the value of the larger jug. One solution will be to fill the small jug and move it to the large jug until it's half full, and the second will be to fill the large jug once and empty it into the smaller N times, until half of it had been emptied.

For example, consider when:

The jugs are A at 4L and B at 1L and the target is 2L
Two optimal solutions are:
Fill A, move A to B, dump B, move A to B
And,
Fill B, move B to A, Fill B, move B to A**

If I have time I'll try to work on a more formal proof for why this would have to be the case.

$\endgroup$
  • $\begingroup$ You're very much on the right track, but the question asked "how full" the larger jug was. You don't need to involve the smaller jug or the target volume in the answer. $\endgroup$ – Sneftel Nov 24 '17 at 20:10
  • $\begingroup$ Can someone fix my spoilers? I'm stuck on mobile right now and can't get them to work... $\endgroup$ – DqwertyC Nov 24 '17 at 20:10
  • $\begingroup$ Well done! Now about that proof.... $\endgroup$ – Sneftel Nov 24 '17 at 20:23
1
$\begingroup$

My guess is

In one case it's empty, in another it's full

Because

You have two jugs, a smaller one, denoted X and a larger one Y (Y > X)
there are two solutions you can get to in two different 4-step ways:
1) x:0 - 0:x - x:x - 2x-y:y
2) 0:y - x:y-x - 0:y-x - y-x:0
for both solutions to have the same amount in the small jug, we need y-x=2x-y, e.g. y=1.5x

So I'm guessing the riddle is, take two jugs size 2,3 L and out 1L in the smaller one

I can't prove (yet?) that it's the only solution, but it's one anyway :)

$\endgroup$
  • $\begingroup$ In the case of 2 and 3 liter jugs, and a 1 liter target, there's only one optimal solution (of two steps): Fill the 3-liter jug from the fountain, then fill the 2-liter jug from the 3-liter jug. $\endgroup$ – Sneftel Nov 24 '17 at 20:07
  • $\begingroup$ @Sneftel you're right, but my answer works if you specify you want 1L in the smaller jar.. don't know if it's legal ? $\endgroup$ – Dotan Nov 24 '17 at 20:09
  • $\begingroup$ It is legal, but the problem only requires "one of the jugs" to contain the target volume. In this case, the optimal solution has it in the larger one. $\endgroup$ – Sneftel Nov 24 '17 at 20:13
  • $\begingroup$ ...Though that was a little unclear in the way I worded the problem. I've added a clarification. $\endgroup$ – Sneftel Nov 24 '17 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.