Hosted by The Math Forum

Problem of the Week 929

Random Walks

_____________________________________________
MacPoW Home ||  Forum PoWs ||  Teachers' Place ||  Student Center ||  Search MacPoW
_____________________________________________

Alice and Bob live at opposite corners of the illustrated grid. Each departs for the house of the other at the same time, walking along the grid at the same speed, and choosing one of the many shortest-length paths uniformly at random. What is the probability that they will meet en route?

You can assume that Alice and Bob each have a stack of maps. On each map one of the possible shortest routes is highlighted, and the stack consists of all possible such maps. Before leaving, Alice and Bob each choose one of the maps at random, with equal probability, and they follow the indicated route.

The exact wording from the source is:

"..independently choosing a path to the other's house with uniform distribution out of all possible minimum-distance paths (that is, all min-distance paths are equally likely)"

It is interesting to note that the problem is different, and I believe you get a different answer, if Alice and Bob randomly choose, with equal probability, between going East and North (or West and South) when they have such a choice.

                                  ------------------Bob 
                                  |         |         | 
                                  |         |         | 
                                  |         |         | 
                                  |         |         | 
                                  --------------------- 
                                  |         |         | 
                                  |         |         | 
                                  |         |         | 
                                  |         |         | 
     -------------------------------------------------- 
     |        |         |         |         |         | 
     |        |         |         |         |         | 
     |        |         |         |         |         | 
     |        |         |         |         |         | 
     -------------------------------------------------- 
     |        |         |         | 
     |        |         |         | 
     |        |         |         | 
     |        |         |         | 
     ------------------------------ 
     |        |         |         | 
     |        |         |         | 
     |        |         |         | 
     |        |         |         | 
     ------------------------------ 
     |        |         |         | 
     |        |         |         | 
     |        |         |         | 
     |        |         |         | 
     Alice-------------------------

Source: International Math Talent Search Round 34, Mathematica and Informatics Quarterly, Feb. 2000.

© Copyright 2001 Stan Wagon. Reproduced with permission.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.

22 Feb 2001