返回题库

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

HMMT February 2018 — Guts Round — Problem 27

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

题目详情

英文原题

  1. [ 15 ] There are 2018 frogs in a pool and there is 1 frog on the shore. In each time-step thereafter, onerandom frog moves position. If it was in the pool, it jumps to the shore, and vice versa. Find theexpected number of time-steps before all frogs are in the pool for the first time.
解析

英文解析

  1. [ 15 ] There are 2018 frogs in a pool and there is 1 frog on the shore. In each time-step thereafter, onerandom frog moves position. If it was in the pool, it jumps to the shore, and vice versa. Find theexpected number of time-steps before all frogs are in the pool for the first time.
    Proposed by: Dhruv Rohatgi
    2018
    Answer: 2 − 1
    Consider the general case of n frogs. Let E be the expected time for all frogs to enter the pool whenii frogs are on the shore and n − i frogs are in the pool. We have E = 0, E = 1 + E , and
    0 n n − 1
    i n − i
    E = E + E + 1
    i i − 1 i +1
    n nfor 0 < i < n . Define f so that
    E = + E .ifii i − 1
    ( n − 1)( n − 2) · · · ( i )
    Then by plugging this equation into the first equation, we can show thatf = n ( n − 1) · · · ( i + 1) + ( n − i ) f .
    i i +1
    Furthermore, we know that f = 1. Thereforen
    ∑nn ! ( n − 1)!
    f =
    i ! ( n − i )!1
    i =1
    ( )
    ∑nn = ( n − 1)!
    i =1 in = ( n − 1)!(2 − 1) .
    Thereforen
    ( n − 1)!(2 − 1)
    E = + E = 2 − 1 .n
    1 0
    ( n − 1)!
    2018
    Plugging in n = 2018 yields E = 2 − 1 . 1