HMMT 二月 2023 · 冲刺赛 · 第 23 题
HMMT February 2023 — Guts Round — Problem 23
题目详情
- [18] A subset S of the set { 1 , 2 , . . . , 10 } is chosen randomly, with all possible subsets being equally likely. Compute the expected number of positive integers which divide the product of the elements of S . (By convention, the product of the elements of the empty set is 1.)
解析
- [18] A subset S of the set { 1 , 2 , . . . , 10 } is chosen randomly, with all possible subsets being equally likely. Compute the expected number of positive integers which divide the product of the elements of S . (By convention, the product of the elements of the empty set is 1.) Proposed by: Sean Li Answer: 375 / 8 Solution: For primes p = 2 , 3 , 5 , 7, let the random variable X denote the number of factors of p in p the product of the elements of S , plus 1. Then we wish to find E ( X X X X ). 2 3 5 7 If there were only prime powers between 1 and 10, then all X would be independent. However, 6 and p 10 are non-prime powers, so we will do casework on whether these elements are included: 1 • Case 1: none included. Note that E ( X | 6 , 10 6 ∈ S ) = 1 + (1 + 2 + 3) = 4, since each 2 2 5 of { 2 , 4 , 8 } has a 1 / 2 chance of being included in S . Similarly, E ( X | 6 , 10 6 ∈ S ) = and 3 2 3 E ( X | 6 , 10 6 ∈ S ) = E ( X | 6 , 10 6 ∈ S ) = . The values of X , X , X , and X are independent 5 7 2 3 5 7 2 5 3 3 45 given that 6 , 10 6 ∈ S , so E ( X X X X | 6 , 10 6 ∈ S ) = 4 · · · = . 2 3 5 7 2 2 2 2 7 • Case 2: 6 included. Now, we have E ( X | 6 ∈ S, 10 6 ∈ S ) = 5 and E ( X | 6 ∈ S, 10 6 ∈ S ) = , 2 3 2 3 since we know 6 ∈ S . We still have E ( X | 6 ∈ S, 10 6 ∈ S ) = E ( X | 6 ∈ S, 10 6 ∈ S ) = . The 5 7 2 values of X , X , X , and X are independent given that 6 ∈ S but 10 6 ∈ S , so E ( X X X X | 2 3 5 7 2 3 5 7 7 3 3 315 6 ∈ S, 10 6 ∈ S ) = 5 · · · = . 2 2 2 8 5 • Case 3: 10 included. We have E ( X | 10 ∈ S, 6 6 ∈ S ) = 5 and E ( X | 10 ∈ S, 6 6 ∈ S ) = , since 2 5 2 5 3 we know 10 ∈ S . We also have E ( X | 10 ∈ S, 6 6 ∈ S ) = and E ( X | 10 ∈ S, 6 6 ∈ S ) = , hence 3 7 2 2 5 5 3 375 E ( X X X X | 10 ∈ S, 6 6 ∈ S ) = 5 · · · = . 2 3 5 7 2 2 2 8 7 • Case 4: 6 and 10 included. We have E ( X | 6 , 10 ∈ S ) = 6, E ( X | 6 , 10 ∈ S ) = , and 2 3 2 5 3 E ( X | 6 , 10 ∈ S ) = . We still have E ( X | 6 , 10 ∈ S ) = , hence E ( X X X X | 6 , 10 ∈ S ) = 5 7 2 3 5 7 2 2 7 5 3 315 6 · · · = . 2 2 2 4 1 45 315 375 315 375 The average of these quantities is ( + + + ) = , as desired. 4 2 8 8 4 8