1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Permutations & Pascal's Triangle

  1. Feb 16, 2009 #1
    1. The problem statement, all variables and given/known data
    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.)


    2. Relevant equations
    (Pascal's Triangle)

    3. 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//
  2. jcsd
  3. Feb 19, 2009 #2
    If I'm correct, you solve for (2-L)^5 + (2-L)

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


    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.
  4. Feb 20, 2009 #3
    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. =]
  5. Feb 20, 2009 #4
    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.
  6. Feb 20, 2009 #5
    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 x1 be the amount of water that flows into row 3. We notice that B(3,1) and B(3,3) receive 0.25x1 while B(3,2) receives 0.5x1. So, after x1 = 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 x2 the amount of water we pour for the next interval under consideration. Notice that 0.5x2 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.25x2. Moreover, B(3,1) and B(3,3) are still being filled. They each, as above, receive 0.25x2. 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 x2 = 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 x3, will trickle into row 4 in the ratio of B(4,1) = B(4,4) = x3/8 and B(4,2) = B(4,3) = 3x3/8. Naturally, B(4,2) and B(4,3) will fill up first. They still need 0.5 liters, so they are full after x3 = 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 x4 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 x4/8 liters of water. B(5,2), B(5,3), and B(5,4) receive 6x4/8 liters of water divided into the ratio 1:2:1 (from the diagram). Hence, B(5,2) = B(5,4) = 3x4/16 liters, while B(5,3) receives 3x4/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 x4/8 liters of water, will need x4 = 20/3. B(5,3) needs 1 liter, at a rate of 3x4/8 liters of water, will need x4 = 8/3. Thus, B(5,3) will fill up faster. After x4 = 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 x5 represent the amount of water poured during the fifth interval, B(6,3) and B(6,4) receives 3x5/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 x5 = 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 x6. 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 x6 = 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 x7. 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 x7 will trickle down into row 5. Of the 5 buckets in that row, 3 are passing 0.75x7 of the water down. Going further, we find that B(6,3) and B(6,4) each get 9x7/32 to fill up 1/8 liters. This will take x7 = 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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook