返回题库

HMMT 二月 2020 · COMB 赛 · 第 5 题

HMMT February 2020 — COMB Round — Problem 5

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. 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 chosen uniformly at random from the range [1 , 1000]. What is the expected number of intervals in S which contain i ?
解析
  1. 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 chosen uniformly at random from the range [1 , 1000]. What is the expected number of intervals in S which contain 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 dividing this value by 1000, where the length of an interval [ i, j ] is given by j − i + 1. An interval may be categorized based on how many times [1 , 1000] must be split to attain it. An interval that is derived from 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), we find 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 ). The 10 total interval length across all splits is equal to 12(1000) − 2 , so our answer is 10 2 12 − = 10 . 976 . 1000