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

HMMT February 2018 — Guts Round — Problem 27

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

解析

[ 15 ] There are 2018 frogs in a pool and there is 1 frog on the shore. In each time-step thereafter, one random frog moves position. If it was in the pool, it jumps to the shore, and vice versa. Find the expected 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 when i i 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 n for 0 < i < n . Define f so that i f i E = + E . i i − 1 ( n − 1)( n − 2) · · · ( i ) Then by plugging this equation into the first equation, we can show that f = n ( n − 1) · · · ( i + 1) + ( n − i ) f . i i +1 Furthermore, we know that f = 1. Therefore n n ∑ n ! ( n − 1)! f = 1 i ! ( n − i )! i =1 ( ) n ∑ n = ( n − 1)! i i =1 n = ( n − 1)!(2 − 1) . Therefore n ( n − 1)!(2 − 1) n E = + E = 2 − 1 . 1 0 ( n − 1)! 2018 Plugging in n = 2018 yields E = 2 − 1 . 1