返回题库

HMMT 二月 2019 · COMB 赛 · 第 4 题

HMMT February 2019 — COMB Round — Problem 4

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

题目详情

英文原题

  1. Yannick is playing a game with 100 rounds, starting with 1 coin. During each round, there is a n %
    chance that he gains an extra coin, where n is the number of coins he has at the beginning of theround. What is the expected number of coins he will have at the end of the game?
解析

英文解析

  1. Yannick is playing a game with 100 rounds, starting with 1 coin. During each round, there is a n %
    chance that he gains an extra coin, where n is the number of coins he has at the beginning of theround. What is the expected number of coins he will have at the end of the game?
    Proposed by: Yuan Yao
    Answer: 1 . 01100
    Let X be the random variable which is the number of coins at the end of round i . Say that X = 1
    i 0
    for convenience. Fix i > 0 and some positive integer x . Conditioning on the event X = x , there arei − 1
    only two cases with positive probability. In particular,
    Pr[ X = x + 1 | X = x ] =xi i − 1
    and 100
    Pr[ X = x | X = x ] = 1 − .xi i − 1
    Therefore 100
    ∑
    E [ X ] = x · Pr[ X = x ]
    i ix> 0
    ( )
    ( )
    ∑
    x x − 1 = x · 1 − Pr[ X = x ] + Pr[ X = x − 1]
    i − 1 i − 1
    100 100
    x> 0
    ∑ ∑
    = x Pr[ X = x ] − x Pr[ X = x − 1]1
    i − 1 i − 1
    x> 0 x> 0100
    ∑ ∑
    1 1
    2 2 + x Pr[ X = x − 1] − x Pr[ X = x ]
    i − 1 i
    100 100
    x> 0 x> 0
    99 1 1 1 = E [ X ] − + E [ X ] +
    i − 1 i − 1
    100 100 50 100 = E [ X ] .101
    i − 1
    (A different way to understand this is that no matter how many coins Yannick has currently (as long 100
    as he does not have more than 100 coins, which is guaranteed in this problem), the expected numberof coins after one round is always 1 . 01 times the current number of coins, so the expected value ismultiplied by 1 . 01 each round.)
    Therefore
    ( )
    101100
    E [ X ] = E [ X ] = 1 . 01 .100
    100 0
    100