1. The classic "Three Jugs" problem: Two friends who have an eight-quart jug of water wish to share it evenly. They also have two empty jars, one holding five quarts, the other three. How can they each measure exactly 4 quarts of water?
For the solution to this problem, I'll label the jugs as the cut-the-knot website labels them: C=8, B=5, and A=3.
The quickest solution is C-B, B-A, A-C, B-A, C-B, B-A, A-C. Another solution that's almost as good is C-A, A-B, C-A, A-B, B-C, A-B, C-A, A-B.
A clever way to visualize the solution uses a graph with Barycentric Coordinates. Here, each point inside the triangle represents a
particular condition of the three containers. The vertices A, B, and C represent the condition that all the water is in container A, B, or C, respectively. That's why the length of the sides of the triangle is equal to the total amount of water. Moving from C to A (or on any parallel line) represents pouring water from C to A.
The points on the line AB represent all the conditions in which C is empty. Similarly, the points on AC represent B empty, and the points on BC represent A empty. For convenience, I call these lines the "C empty," "B empty," and "A empty" lines.
Now, you may notice the blue parallelogram in this diagram. It's there to show the limits of the containers. Since A can hold only three
quarts, there is a blue line which is three units away from the "A empty" line. Similarly, there is a line 5 units away from the "B empty" line.
Point C is darkened to show that this is the initial condition. The valid moves move the condition of the containers along the pink (or blue) lines, and must end at the blue line, which represents the condition in which one of the containers has been completely filled or completely emptied.
As you move from one state to another, it seems as if you are bouncing off the blue line like a billiard ball. Here's a diagram of one solution, C-B, B-A, A-C, B-A, C-B, B-A, A-C:
Try to follow the sequence of moves, remembering that A-C, for example, means you're traveling along the line parallel to AC in the direction of C. Now here's the second solution we offered, C-A, A-B, C-A, A-B, B-C, A-B, C-A, A-B:
2. 3 people carry 5 pails (each with capacity 8L) to a place where there are 3 springs.
One of the springs gives 2L/minute and the other two give 1L/minute.
It is not possible to use one spring to fill two pails simultaneously.
It takes less than 2 minutes and more than 1 minute to take a pail from one spring to another.
What is the shortest time it takes for them to fill all five pails? How?
They can fill the pails in 10 minutes.
First, I'll try to put some bounds on the possible time. The aggregate flow is 4L/minute, and the total pail capacity is 40L, so the best one could hope for is 10 minutes, and then only if water is flowing continuously into all three pails for the full 10 minutes. A simple-minded plan would be to fill one pail each at the slow spring, and 3 pails at the fast spring, which would take 12 minutes. So the answer has to between 10 and 12 minutes, inclusive.
The simple-minded plan fills a bucket at each of the slow springs in 8 minutes, wasting 2 minutes at each spring. To correct this problem, it is necessary to bring a bucket to each of the slow springs with 2L of available capacity in each bucket so they can be filled to the top in the last two minutes.
This is certainly possible. Here's one approach:
Begin by positioning three buckets at the fast spring, and one at each of the slow springs. As soon as the water begins pouring into the buckets, the two slow-spring attendants walk to the fast spring. At the fast spring, as soon as a bucket is 6L (3/4 of the way) full, which happens at the 3-minute mark, switch buckets, and bring the 3/4-full one to one of the slow springs. Then, back at the fast spring, when the second bucket gets 3/4 full, at the 6-minute mark, switch buckets again, and bring the 3/4-full one to the other slow spring. Both 3/4-full buckets will arrive at slow springs in time to continue filling them, resulting in all buckets being exactly full after exactly 10 minutes.
Another approach would be to fill the first bucket just half-way at the fast spring (2 minutes), switch buckets, bring it to one of the slow springs, and get back to the fast spring before the second bucket fills. Switch buckets again at the 6-minute mark, and fill the third bucket by 10 minutes. Meanwhile at the first slow spring, when the bucket gets 3/4 full, switch it with the 1/2 full bucket, and bring the 3/4 full bucket to the second spring.
Derek Lomax contributed a very fine idea: a colorful graphic that illustrates his solution, which was also quite good:
Jonathanasdf provided a solution that is the best in the sense that it requires the minimum amount of water-carrying from spring to spring -- just 4 liters are moved in all: