PUMaC 2020 · 组合（A 组） · 第 7 题
PUMaC 2020 — Combinatorics (Division A) — Problem 7
题目详情
- Let f be defined as below for integers n ≥ 0 and a , a , ... such that a is finite: 0 1 i i ≥ 0 { a n = 0 2020 ∑ f ( n ; a , a , ... ) = . a f ( n − 1; a ,...,a ,a − 1 ,a +1 ,a ,... ) 0 1 i 0 i − 1 i i +1 i +2 i ≥ 0 ∑ n > 0 a i i ≥ 0 2 Find the nearest integer to f (2020 ; 2020 , 0 , 0 , ... ). 1
解析
- Let f be defined as below for integers n ≥ 0 and a , a , ... such that a is finite: 0 1 i i ≥ 0 { a n = 0 2020 ∑ f ( n ; a , a , ... ) = . a f ( n − 1; a ,...,a ,a − 1 ,a +1 ,a ,... ) 0 1 i 0 i − 1 i i +1 i +2 i ≥ 0 ∑ n > 0 a i i ≥ 0 2 Find the nearest integer to f (2020 ; 2020 , 0 , 0 , ... ). Proposed by Daniel Carter Answer: 18 . Solution: Consider a balls each uniformly placed into b bins. The value of f ( a ; b, 0 , 0 , ... ) is the expected number of bins containing exactly 2020 balls. In general, the value of f ( n ; a , a , ... ) 0 1 is the expected number of bins containing exactly 2020 balls given that there are n balls left to place, a bins with no balls, a bins with exactly 1 ball, and so on: if there are no balls 0 1 left to place the expected number of bins with 2020 balls is a , otherwise we place one ball 2020 ∑ and it has an a / a chance of being placed into a bin that currently has k balls and the k i i ≥ 0 second case of f computes the sum of this over all k . By linearity of expectation, the expected number of bins containing 2020 balls when there are 2 2020 bins and 2020 total balls is equal to the sum of the probability that any particular bin has 2020 balls over all bins. The chance that any particular bin has 2020 balls is equal to 2 ( ) ( ) ( ) 2 2020 2020 − 2020 2020 1 2020 − 1 , so the desired value of f is 2020 times this. 2020 2020 2020 √ n Now using Stirling’s approximation of the factorial, n ! ≈ 2 πn ( n/e ) , this is very close to 2 ( ) x √ 2 2 x ( ) ( ) 2 x x − x 2 πx e 1 x − 1 x √ 2 √ ( ) ( ) x − x x 2 x x − x x x 2 2 πx 2 π ( x − x ) e e √ 2020 √ √ where x = 2020. This valiantly simplifies to just , which is very close to 1010 /π . 2 π 2019 You can use your favorite approximation of π (in fact π ≈ 3 is good enough) to find 1010 /π ≈ 2 321 . 5 is very close to 324 = 18 , so the answer is 18.