I read this problem a few days ago and just decided to give it some thought now (I would love to know the correct solution). The answer will certainly be a fun

I read this problem a few days ago and just decided to give it some thought now (I would love to know the correct solution). The answer will certainly be a function of n (because, for example, I could give you n = 1001 and that should have 0 probability whereas if I were to give you n = 1, that would have a very high probability). My first thought was to write out a recurrence relation f of n and k (where n is the current level and k is the number of moves left). From this, we get: f(n, k) = .5f(n-1, k-1) + .5f(n+1, k-1) with f(n, k) = 0 when n > k and f(0, k) = 1. So to solve this, we just take f(n, 1000) = [a rapidly exploding function]. Any thoughts?