Permutations & Pascal's Triangle

In summary, we pour water into the top bucket and as it fills, it overflows into the buckets below. We can think of this process in discrete intervals of time. Each interval, a certain amount of water is poured and we see which buckets fill up first. We can use this information to find out how much water will be needed for the next interval. In this case, if we have 2-L buckets, the final amount of water needed will be 30.8 L.
  • #1
Sweeneykill
2
0

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.)

Bucket.jpg


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//
 
Physics news on Phys.org
  • #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:

(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.
 
  • #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. =]
 
  • #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.
 
  • #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.
 

What is a permutation?

A permutation is a way of arranging a set of objects in a specific order. It is a mathematical concept that is used to calculate the number of possible arrangements of a given set of objects.

What is the formula for calculating permutations?

The formula for calculating permutations is n! / (n-r)!, where n is the total number of objects and r is the number of objects being arranged. This formula represents the number of ways that r objects can be arranged from a set of n objects.

What is Pascal's Triangle?

Pascal's Triangle is a triangular arrangement of numbers that was named after the French mathematician Blaise Pascal. Each number in the triangle is the sum of the two numbers directly above it.

How is Pascal's Triangle used in permutations?

Pascal's Triangle is used in permutations to help calculate the number of possible arrangements of a set of objects. The numbers in the triangle represent the number of ways that a certain number of objects can be chosen from a larger set of objects.

What other applications does Pascal's Triangle have?

Pascal's Triangle has many other applications, including in probability, binomial expansions, and the study of combinatorics. It is also used in computer science, particularly in programming languages that involve recursion.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
5
Views
3K
  • Precalculus Mathematics Homework Help
Replies
3
Views
843
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Precalculus Mathematics Homework Help
Replies
2
Views
2K
  • Introductory Physics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
6
Views
2K
  • Introductory Physics Homework Help
Replies
12
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
13
Views
3K
Back
Top