jump to navigation

Problem of the Day #206: Climbing Stairs October 11, 2011

Posted by Billy in : potd , trackback

Albert is climbing a staircase with $n$ stairs. He is currently at the bottom of the stairs. For any step, let $m$ be the number of steps above him until the top. Each turn, Albert has a $\frac{1}{2^k}$ chance of going up $k$ stairs and a $\frac{1}{2^m}$ chance of staying on the same step. What is the expected number of turns it will take Albert to reach the top of the stairs?


no comments yet - be the first?