Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

There are n red & n blue jugs of different sizes and shapes. All red jugs hold different amounts of water as the blue ones. For every red jug, there is a blue jug that holds the same amount of water, and vice versa. The task is to find a grouping of the jugs into pairs of red and blue jugs that hold the same amount of water.

Operation allowed: Pick a pair of jugs in which one is red and one is blue, fill the red jug with water and then pour the water into the blue jug. This operation will tell you whether the red or the blue jug can hold more water, or if they are of the same volume. Assume that such a comparison takes one time unit. Your goal is to find an algorithm that makes a minimum number of comparisons to determine the grouping.

You may not directly compare two red jugs or two blue jugs.

  1. Prove a lower bound of Θ(n lg n) for the number of comparisons an algorithm solving this problem must make.

  2. Give a randomized algorithm whose expected number of comparisons is O(n lg n)

share|improve this question

closed as off topic by Daniel Moskovich, Ryan Budney, Yemon Choi, Simon Thomas, Theo Johnson-Freyd Sep 7 '10 at 0:45

Questions on MathOverflow are expected to relate to research level mathematics within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
You should search the net before asking. This madhurtanwani.blogspot.com/2009/08/algo-water-jugs-problem.html seems to answer your question. Moreover, your question sounds like an exercise from an algorithms textbook to me. –  Somnath Basu Sep 6 '10 at 18:05

2 Answers 2

up vote 1 down vote accepted

The lower bound can be gotten the same way we get a lower bound of $O(n \log n)$ for comparison-based sorting. Each comparison of jugs produces one of three possible outcomes, which is at most $\log_2 3 = O(1)$ bits of information. But we need to distinguish among $n!$ possible matchings of red and blue jugs, which requires $\log_2(n!) = O(n \log n)$ bits.

The overall problem can be solved with something very close to quicksort. Pick a red jug arbitrarily. Compare it against every blue jug. This will separate the blue jugs into one that is the same same size as the chosen red jug, a set of smaller blue jugs, and a set of bigger blue jugs. Use the same-size blue jugs to partition the red jugs the same way. Recursively apply this algorithm to the sets of larger and smaller red and blue jugs. The recursion bottoms out when there is only one jug of each color in a set.

share|improve this answer

See "Matching nuts and bolts" by Alon et al from SODA 1994, on exactly this problem.

share|improve this answer

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