HMMT 二月 2023 · 冲刺赛 · 第 35 题
HMMT February 2023 — Guts Round — Problem 35
题目详情
- [25] The Fibonacci numbers are defined recursively by F = 0, F = 1, and F = F + F for i ≥ 2. 0 1 i i − 1 i − 2 √ √ √ 3 3 3 Given 30 wooden blocks of weights F , F , . . . , F , estimate the number of ways to paint each 2 3 31 block either red or blue such that the total weight of the red blocks and the total weight of the blue blocks differ by at most 1. 8 8 Submit a positive integer E . If the correct answer is A , you will receive b 25 min(( E/A ) , ( A/E ) ) c points. (If you do not submit a positive integer, you will receive zero points for this question.)
解析
- [25] The Fibonacci numbers are defined recursively by F = 0, F = 1, and F = F + F for i ≥ 2. 0 1 i i − 1 i − 2 √ √ √ 3 3 3 Given 30 wooden blocks of weights F , F , . . . , F , estimate the number of ways to paint each 2 3 31 block either red or blue such that the total weight of the red blocks and the total weight of the blue blocks differ by at most 1. 8 8 Submit a positive integer E . If the correct answer is A , you will receive b 25 min(( E/A ) , ( A/E ) ) c points. (If you do not submit a positive integer, you will receive zero points for this question.) Proposed by: Albert Wang, Luke Robitaille Answer: 3892346 Solution: To get within an order of magnitude, one approach is to let X be a random variable n √ 3 which takes the value ± F , with the sign chosen uniformly at random. We want the probability that n ∑ 31 S = X is in [ − 1 , 1]. We can attempt to approximate the distribution of S as normal (this is i i =2 loosely justified because it is the sum of many independent random variables). Using the approximation √ 1 1+ 5 n √ F ≈ ϕ for φ = , the variance of S is: n 2 5 31 ∑ Var( S ) = Var( X ) i i =2 31 ∑ 2 / 3 = F i i =2 31 ∑ − 1 / 3 2 i/ 3 ≈ 5 ϕ i =2 ( ) 62 / 3 ϕ − 1 / 3 ≈ 5 · − 2 / 3 1 − ϕ 1 √ Now, we use the fact that if S is standard normal, then the probability that S ∈ [ − 1 , 1] is Var( S ) approximately √ √ − 2 / 3 1 2 1 / 3 1 − ϕ 2 · 5 √ √ · ≈ · π 31 / 3 ϕ 2 π Var( S ) 30 When we multiply this by 2 , we get an approximation of E ≈ 4064598, which achieves A/E ≈ 0 . 96 and would score 17 out of 25 points.