返回题库

HMMT 二月 2018 · ALGNT 赛 · 第 7 题

HMMT February 2018 — ALGNT Round — Problem 7

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

题目详情

英文原题

  1. Rachel has the number 1000 in her hands. When she puts the number x in her left pocket, the number − 1
    changes to x + 1. When she puts the number x in her right pocket, the number changes to x . Eachminute, she flips a fair coin. If it lands heads, she puts the number into her left pocket, and if itlands tails, she puts it into her right pocket. She then takes the new number out of her pocket. If theexpected value of the number in Rachel’s hands after eight minutes is E , then compute b c .E
    10
解析

英文解析

  1. Rachel has the number 1000 in her hands. When she puts the number x in her left pocket, the number − 1
    changes to x + 1. When she puts the number x in her right pocket, the number changes to x . Eachminute, she flips a fair coin. If it lands heads, she puts the number into her left pocket, and if itlands tails, she puts it into her right pocket. She then takes the new number out of her pocket. If theexpected value of the number in Rachel’s hands after eight minutes is E , then compute b c .E
    Proposed by: Kevin Sun 10
    Answer: 13
    Call a real number very large if x ∈ [1000 , 1008], very small if x ∈ [0 , ], and medium-sized if 1
    1000
    x ∈ [ , 8]. Every number Rachel is ever holding after at most 8 steps will fall under one of these 1
    categories. Therefore the main contribution to E will come from the probability that Rachel is holding 8
    a number at least 1000 at the end.
    Note that if her number ever becomes medium-sized, it will never become very large or very smallagain. Therefore the only way her number ends up above 1000 is if the sequence of moves consists of − 1
    x → x + 1 moves and consecutive pairs of x → x moves. Out of the 256 possible move sequences,
    the number of ways for the number to stay above 1000 is the number of ways of partitioning 8 into anordered sum of 1 and 2, or the ninth Fibonacci number F = 34.
    Therefore 9
    34 34
    · 1000 ≤ E ≤ · 1000 + 8 ,
    256 256
    where · 1000 ≈ 132 . 8. Furthermore, the extra contribution will certainly not exceed 7, so we get 34
    E256
    that b c = 13.
    (The actual value of E is 10
    1538545594943410132524842390483285519695831541468827074238984121209064525621
    ,
    11415831910281261197289931074429782903650103348754306523894286954489856000
    which is approximately equal to 134 . 77297. We can see that the extra contribution is about 2 and isvery insignificant.)