返回题库

HMMT 二月 2018 · 冲刺赛 · 第 25 题

HMMT February 2018 — Guts Round — Problem 25

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  1. [ 15 ] Fran writes the numbers 1 , 2 , 3 , . . . , 20 on a chalkboard. Then she erases all the numbers bymaking a series of moves; in each move, she chooses a number n uniformly at random from the setof all numbers still on the chalkboard, and then erases all of the divisors of n that are still on thechalkboard (including n itself). What is the expected number of moves that Fran must make to eraseall the numbers?
    ° °
解析

英文解析

  1. [ 15 ] Fran writes the numbers 1 , 2 , 3 , . . . , 20 on a chalkboard. Then she erases all the numbers bymaking a series of moves; in each move, she chooses a number n uniformly at random from the setof all numbers still on the chalkboard, and then erases all of the divisors of n that are still on thechalkboard (including n itself). What is the expected number of moves that Fran must make to eraseall the numbers?
    Proposed by: Michael Tang
    Answer:131
    For each n , 1 ≤ n ≤ 20, consider the first time that Fran chooses one of the multiples of n . It is in 10
    this move that n is erased, and all the multiples of n at most 20 are equally likely to be chosen forthis move. Hence this is the only move in which Fran could possibly choose n ; since there are b 20 /n cmultiples of n at most 20, this means that the probability that n is ever chosen is 1 / b 20 /n c . Thereforethe expected number of moves is
    ∑20
    E =1
    b 20 /n cn =1
    ( )
    1 1 1 1 1 1 1 131 = + + + + + + 4 + 10 (1) = .
    20 10 6 5 4 3 2 10
    (This sum is easier to compute than it may seem, if one notes that 1 / 20 + 1 / 5 + 1 / 4 = 1 / 2 and
    1 / 6 + 1 / 3 = 1 / 2).
    ° °