返回题库

HMMT 二月 2020 · COMB 赛 · 第 5 题

HMMT February 2020 — COMB Round — Problem 5

专题
Contest 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 chosenuniformly at random from the range [1 , 1000]. What is the expected number of intervals in S whichcontain 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 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