PUMaC 2020 · 组合（B 组） · 第 6 题
PUMaC 2020 — Combinatorics (Division B) — Problem 6
题目详情
- Billy the baker makes a bunch of loaves of bread every day, and sells them in bundles of size 1 , 2 , or 3. On one particular day, there are 375 orders, 125 for each bundle type. As such, Billy goes ahead and makes just enough loaves of bread to meet all the orders. Whenever Billy makes loaves, some get burned, and are not sellable. For nonnegative i less than or equal to the total number of loaves, the probability that exactly i loaves are sellable to customers is i inversely proportional to 2 (otherwise, it’s 0). Once he makes the loaves, he distributes out all of the sellable loaves of bread to some subset of these customers (each of whom will only accept their desired bundle of bread), without worrying about the order in which he gives them b a out. If the expected number of ways Billy can distribute the bread is of the form , find c 2 − 1 a + b + c.
解析
- Billy the baker makes a bunch of loaves of bread every day, and sells them in bundles of size 1 , 2 , or 3. On one particular day, there are 375 orders, 125 for each bundle type. As such, Billy goes ahead and makes just enough loaves of bread to meet all the orders. Whenever Billy makes loaves, some get burned, and are not sellable. For nonnegative i less than or equal to the total number of loaves, the probability that exactly i loaves are sellable to customers is i inversely proportional to 2 (otherwise, it’s 0). Once he makes the loaves, he distributes out all of the sellable loaves of bread to some subset of these customers (each of whom will only accept their desired bundle of bread), without worrying about the order in which he gives them b a out. If the expected number of ways Billy can distribute the bread is of the form , find c 2 − 1 a + b + c. Proposed by Frank Lu Answer: 1011 Solution: Note that the number of loaves Billy attempts to make is 125(1 + 2 + 3) = 750. We 750 ∑ want to find p ( i ) · a , where p ( i ) is the probability of having i good loaves to give out, and i i =1 a is the number of ways to distribute i good loaves. We’re given that p ( i ) is proportional to i 1 C , meaning p ( i ) = for some constant C . i i 2 2 ∑ ∑ 750 750 1 1 Probabilities sum to one, so 1 = p ( i ) = C = C · (2 − ) . From here, there’s i 750 i =0 i =0 2 2 two finishes: ( )( )( ) ∑ 125 125 125 Finish 1 : Note that a = . Hence, observe that our sum is equal i x x x 1 2 3 x +2 x +3 x = i 1 2 3 750 ( )( )( ) ∑ ∑ 125 125 125 C to . i 2 x x x 1 2 3 i =0 x +2 x +3 x = i 1 2 3 125 125 125 ( )( )( ) ∑ ∑ ∑ 125 125 125 C However, this is actually equivalent to . Now, remark x +2 x +3 x 1 2 3 x x x 2 1 2 3 x =0 x =0 x =0 1 2 3 ( ) ∑ 125 125 1 that this is the product of three terms of the form , which we can write as ix x =0 i 2 x i i 1 125 (1 + ) by using the binomial theorem. Hence, we see that our desired expression is equal i 2 750 375 125 125 3 5 9 125 2 3 · 5 135 to C ( · · ) , which upon substituting is · = , giving us the answer 751 750 751 2 4 8 2 − 1 2 2 − 1 135 + 125 + 751 = 1011 . 3 Finish 2 (Ben Zenker) Consider the generating function (( ) ( ) ( ) ( ) ( ) ) 125 125 125 125 125 0 1 2 124 125 f ( x ) = x + x + x + ... + x + x · 0 1 2 124 125 (( ) ( ) ( ) ( ) ) (( ) ( ) ( ) ) 125 125 125 125 125 125 125 0 2 248 250 0 3 375 x + x + ... + x + x · x + x + ... + x . 0 1 124 125 0 1 125 n The coefficient of x in this function is exactly the number of ways to choose a distribution of n loaves to customers. 750 ∑ 125 2 125 3 125 i Using the binomial theorem, f ( x ) = (1 + x ) (1 + x ) (1 + x ) = x · a . Hence, i i =0 ( ) ( ) ( ) ( ) ( ) ∑ i 125 125 125 750 1 1 1 1 1 1 f ( ) = · a , so the value we want is C · f = C 1 + 1 + 1 + , i 2 i =0 2 2 2 4 8 125 135 giving = ⇒ 1011 as above. 751 2 − 1