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, 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.
解析
英文解析
- [ 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