HMMT 二月 2020 · COMB 赛 · 第 5 题
HMMT February 2020 — COMB Round — Problem 5
题目详情
英文原题
- Let S be a set of intervals defined recursively as follows:
• Initially, [1 , 1000] is the only interval in S .
[ ⌊ ⌋] [⌊ ⌋ ]
l + r l + r
• If l 6 = r and [ l, r ] ∈ S , then both l, , + 1 , r ∈ S .
2 2
(Note that S can contain intervals such as [1 , 1], which contain a single integer.) An integer i is chosenuniformly at random from the range [1 , 1000]. What is the expected number of intervals in S whichcontain i ?
解析
英文解析
- Let S be a set of intervals defined recursively as follows:
• Initially, [1 , 1000] is the only interval in S .
[ ⌊ ⌋] [⌊ ⌋ ]
l + r l + r
• If l 6 = r and [ l, r ] ∈ S , then both l, , + 1 , r ∈ S .
2 2
(Note that S can contain intervals such as [1 , 1], which contain a single integer.) An integer i is chosenuniformly at random from the range [1 , 1000]. What is the expected number of intervals in S whichcontain i ?
Proposed by: Benjamin Qi
Answer: 10 . 976
Solution: The answer is given by computing the sum of the lengths of all intervals in S and dividingthis value by 1000, where the length of an interval [ i, j ] is given by j − i + 1. An interval may becategorized based on how many times [1 , 1000] must be split to attain it. An interval that is derivedfrom splitting [1 , 1000] k times will be called a k -split .
The only 0-split is [1 , 1000], with a total length of 1000. The 1-splits are [1 , 500] and [501 , 1000], with a total length of 1000. As long as none of the k -splits have length 1, the ( k + 1)-splits will have the same total length. Since the length of the intervals is reduced by half each time (rounded down), wefind that the sum of the lengths of the k -splits is 1000 for 0 ≤ k ≤ 9.
10 9
Note that the 9-splits consist of 2 − 1000 intervals of length 1 and 1000 − 2 intervals of length 2.
9 9
Then the 10-splits consist of 2(1000 − 2 ) intervals of length 1, with total length 2(1000 − 2 ). Thetotal interval length across all splits is equal to 12(1000) − 2 , so our answer is 10
12 − = 10 . 976 .210
1000