Permutations & Pascal's Triangle

[Sweeneykill]

Homework Statement

Water is poured into the top bucket of a triangular stack of 2-L buckets. When each bucket is full, the water overflows equally on both sides into the buckets immediately below. How much water will have been poured into the top bucket when at least one of the buckets in the bottom row is full? (There are 6 rows, not starting from 0, but starting from 1, 2, 3, etc.)

Homework Equations

(Pascal's Triangle)

The Attempt at a Solution

I know if the buckets are 1 liter ones, the answer is about 15.4 or exactly 15.4. Therefore if it is 2 - L it should be 30.8. However, I do not understand why, or how to show the relavent information. In order to get marks on this on my test, I will need to show the FULL explanation as to how I got 30.8//

 

[Mezzlegasm]

If I'm correct, you solve for (2-L)^5 + (2-L)

so you fill in the triangle up to five and you have:

(2^5)+(5(2^4-L))+(10(2^3-L^2))+(10(2^2-L^3))+(5(2-L^4))+(L^5)

That should be right. You can fill in the rest from there. What I don't understand is how you got 15.4. is it 2 liter buckets or 2-L buckets? if it's 2 liter buckets than it should be 32 just by addition I think.

 

[Sweeneykill]

The answer in the book is 30.8, or might be 32, not sure I will have to double check.
Anyway, I think I have some idea of how to solve it. So thanks for the help. =]

 

[kbaumen]

Well, seems quite straightforward. Not much math involved. It's more like logical deduction. Definitely all the water in the system will have been poured in the first bucket in the beginning, so simply add volumes. You have 17 full buckets and 2 half-full, so that gives a total of 17 * 2 + 2 * 1 = 36 L of water.

 

[Tedjn]

One way to think about this question is to think in discrete intervals of time. Let us see how we would get 15.4 L as the final amount needed for the original question. Hopefully, then, you will be able to go through the argument and see why it scales the way it does for 2 liter buckets, or, in general, S liter buckets.

To make talking about our buckets easier, we number them: the jth bucket in the ith row will be denoted B(i,j). Before we go on, notice that the buckets in the middle will fill up more quickly. In particular, the rate at which the bucket fills depends on how many paths the water has to get to it from the top. This number, as you probably learned, is related to Pascal's triangle. However, in this problem, the difficulty is that each bucket must be filled completely before any water is allowed to move downwards. For any bucket B(i,j), some paths to it may be unavailable for some intervals of time (i.e. while the bucket above B(i,j) is still being filled).

Now, we begin pouring water into the top bucket. After 1 liter, the top bucket is filled. After 3 liters, the entire second row is filled too. These two intervals are clear. Now, all the water poured into the top bucket begins to fill row 3. Let x₁ be the amount of water that flows into row 3. We notice that B(3,1) and B(3,3) receive 0.25x₁ while B(3,2) receives 0.5x₁. So, after x₁ = 2 (i.e. two more liters have been poured), B(3,2) is filled while B(3,1) and B(3,3) each contain 0.5 liters of water. So far, we have poured 5 liters.

Now, let us call x₂ the amount of water we pour for the next interval under consideration. Notice that 0.5x₂ flows into B(3,2) which, since it's filled, passes this water equally to B(4,2) and B(4,3). Each of these buckets therefore receives 0.25x₂. Moreover, B(3,1) and B(3,3) are still being filled. They each, as above, receive 0.25x₂. Clearly, B(3,1) and B(3,3) will fill up faster than B(4,2) and B(4,3). They still need 0.5 liters, they will be filled after x₂ = 2. Thus, after 2 more liters have been poured, the situation is now as follows: third row of buckets is now filled. B(4,1) = B(4,4) = 0 liters, B(4,2) = B(4,3) = 0.5 liters. Total liters poured is 7 liters.

Since the 3rd row is filled, all the additional water poured in the next interval, call it x₃, will trickle into row 4 in the ratio of B(4,1) = B(4,4) = x₃/8 and B(4,2) = B(4,3) = 3x₃/8. Naturally, B(4,2) and B(4,3) will fill up first. They still need 0.5 liters, so they are full after x₃ = 4/3 liters. The situation now is: B(4,1) = B(4,4) = 1/6, B(4,2) = B(4,3) = 1 (full). Total liters poured is 7 + 4/3 liters.

In the next interval x₄ buckets B(4,1), B(4,4), B(5,2), B(5,3), B(5,4) are being filled. B(4,1) and B(4,4) continue to receive x₄/8 liters of water. B(5,2), B(5,3), and B(5,4) receive 6x₄/8 liters of water divided into the ratio 1:2:1 (from the diagram). Hence, B(5,2) = B(5,4) = 3x₄/16 liters, while B(5,3) receives 3x₄/8 liters of water. We wish to find out which bucket will fill up first, so we can then further divide into the next time interval (in which new water paths are allowed). Clearly, B(5,3) will fill up faster than both B(5,2) and B(5,4), but will it fill up faster than B(4,1) and B(4,4)? B(4,1) needs 5/6 liters, at a rate of x₄/8 liters of water, will need x₄ = 20/3. B(5,3) needs 1 liter, at a rate of 3x₄/8 liters of water, will need x₄ = 8/3. Thus, B(5,3) will fill up faster. After x₄ = 8/3 more liters have been poured, the situation is now: B(4,1) = B(4,4) = 1/2 liters, B(5,2) = B(5,4) = 1/2 liters, B(5,3) = 1 liter (full). Total liters poured is 11 liters.

We are getting closer to the end. Next, we see that B(5,3) empties into B(6,3) and B(6,4) at half the rate of water that B(5,3) is receiving. That means, if we let x₅ represent the amount of water poured during the fifth interval, B(6,3) and B(6,4) receives 3x₅/16. Since B(5,2) and B(5,4) receive water in the same proportion, they will fill up first. They will also fill up faster than B(4,1) and B(4,4), because they start off with the same amount of water and the fifth row buckets receive more. As a result, we solve for when B(5,2) and B(5,4) is filled, leading to x₅ = 8/3. In the end, we have B(4,1) = B(4,4) = 5/6 liters, B(5,2) = B(5,4) = 1 liters (full), B(6,3) = B(6,4) = 1/2 liters. Total liters poured is 11 + 8/3 liters.

Period x₆. It is pretty clear that B(4,1) and B(4,4) will fill up before any other buckets, although you can argue through it rigorously. Since this post is already getting long, I'll just say that we'll set x₆ = 4/3 liters and give you the results for the new buckets. Afterwards, we have B(4,1) = B(4,4) = 1 liter (finally full), B(6,2) = B(6,5) = 1/8 liters, B(6,3) = B(6,4) = 7/8 liters. Total liters poured is 15 liters.

Last period x₇. We can work it out, but because B(6,3) and B(6,4) are closest to being filled, and they receive water the fastest, we know that they will be filled after this period. Row 4 is finally completely filled, so all water x₇ will trickle down into row 5. Of the 5 buckets in that row, 3 are passing 0.75x₇ of the water down. Going further, we find that B(6,3) and B(6,4) each get 9x₇/32 to fill up 1/8 liters. This will take x₇ = 4/9.

Therefore, total amount of water poured for the first bucket(s) B(6,3) and B(6,4) to be filled is 15 + 4/9 = 15.44 L.

While straightforward, this turned out to be fairly complicated. I don't know how to generalize it to more buckets. Probably there would be some sort of approximation process involved that I am unfamiliar with. Nonetheless, you should be able to go back through this argument and argue why doubling the size of each bucket doubles the total amount of water poured.