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=

n-1

\

( 1/2 )^(m+k+1) * (m+k)C(m) * (n-k+1)/2 .

/

k=

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=

and

n-1

\

g(m,n) = > ( 1/2 )^k * (m+k)C(m) .

/

k=

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=

- (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).