==> probability/lights.s <== Let E(m,n) be this number, and let (x)C(y) = x!/(y! (x-y)!). A model for this problem is the following nxm grid: ^ B---+---+---+ ... +---+---+---+ (m,0) | | | | | | | | | N +---+---+---+ ... +---+---+---+ (m,1) <--W + E--> : : : : : : : : S +---+---+---+ ... +---+---+---+ (m,n-1) | | | | | | | | | v +---+---+---+ ... +---+---+---E (m,n) where each + represents a traffic light. We can consider each traffic light to be a direction pointer, with an equal chance of pointing either east or south. IMHO, the best way to approach this problem is to ask: what is the probability that edge-light (x,y) will be the first red edge-light that the pedestrian encounters? This is easy to answer; since the only way to reach (x,y) is by going south x times and east y times, in any order, we see that there are (x+y)C(x) possible paths from (0,0) to (x,y). Since each of these has probability (1/2)^(x+y+1) of occuring, we see that the the probability we are looking for is (1/2)^(x+y+1)*(x+y)C(x). Multiplying this by the expected number of red lights that will be encountered from that point, (n-k+1)/2, we see that m-1 ----- \ E(m,n) = > ( 1/2 )^(n+k+1) * (n+k)C(n) * (m-k+1)/2 / ----- k=0 n-1 ----- \ + > ( 1/2 )^(m+k+1) * (m+k)C(m) * (n-k+1)/2 . / ----- k=0 Are we done? No! Putting on our Captain Clever Cap, we define n-1 ----- \ f(m,n) = > ( 1/2 )^k * (m+k)C(m) * k / ----- k=0 and n-1 ----- \ g(m,n) = > ( 1/2 )^k * (m+k)C(m) . / ----- k=0 Now, we know that n ----- \ f(m,n)/2 = > ( 1/2 )^k * (m+k-1)C(m) * (k-1) / ----- k=1 and since f(m,n)/2 = f(m,n) - f(m,n)/2, we get that n-1 ----- \ f(m,n)/2 = > ( 1/2 )^k * ( (m+k)C(m) * k - (m+k-1)C(m) * (k-1) ) / ----- k=1 - (1/2)^n * (m+n-1)C(m) * (n-1) n-2 ----- \ = > ( 1/2 )^(k+1) * (m+k)C(m) * (m+1) / ----- k=0 - (1/2)^n * (m+n-1)C(m) * (n-1) = (m+1)/2 * (g(m,n) - (1/2)^(n-1)*(m+n-1)C(m)) - (1/2)^n*(m+n-1)C(m)*(n-1) therefore f(m,n) = (m+1) * g(m,n) - (n+m) * (1/2)^(n-1) * (m+n-1)C(m) . Now, E(m,n) = (n+1) * (1/2)^(m+2) * g(m,n) - (1/2)^(m+2) * f(m,n) + (m+1) * (1/2)^(n+2) * g(n,m) - (1/2)^(n+2) * f(n,m) = (m+n) * (1/2)^(n+m+1) * (m+n)C(m) + (m-n) * (1/2)^(n+2) * g(n,m) + (n-m) * (1/2)^(m+2) * g(m,n) . Setting m=n in this formula, we see that E(n,n) = n * (1/2)^(2n) * (2n)C(n), and applying Stirling's theorem we get the beautiful asymptotic formula E(n,n) ~ sqrt(n/pi).