Thursday, October 9, 2008

City Roads

This is a problem that I conceived while walking the streets of Pune.

So imagine a city which has 2 sets of mutually perpendicular roads. That is one set of 2m roads parallel to each other and another set of 2n roads parallel to each other but perpendicular to the first set.
In other words the city can be imagined as a net or a grid with 2 sets of parallel lines.
The squares in the city can then be seen as the meeting points of one line from the first set and another from the other set. Barring the squares on the 1st and the last roads of both the sets, each square will have 4 roads merging into it.
The problem then is to find out what is the average number of squares you cross starting from the coordinates (m,n) before you reach a square already crossed before. We of course assume that at each square there is a equal chance that you choose any of the available roads including the one you came from.

Level: Moderate

PS: I happened to assume this problem as a good coffee table conversation, an assumption I later found out to be fallacious.

No comments: