By Murray Bourne, 09 Aug 2010
Many cities are built on a grid pattern where city blocks are approximately square. The grey dotted lines in the following diagrams represent streets.
A taxi driver needs to go from point C to B. She decides to take the following route (depending on her local knowledge of traffic and one way streets and so on), where she heads north along CD, turns East for DF, then North again, and so on until she reaches B.
Or she could have more simply travelled from C to A, then A to B. If CA = AB = 1 km, then the total journey is 2 km, no matter which route she took. (Distance CD = 200 m and there are 10 such blocks, so 2 km is the total distance.)
This gives rise to an interesting type of geometry called Taxicab Geometry, first proposed by Hermann Minkowski in the 19th century.
How Many Routes?
There are clearly many different ways of going from C to B. If we assume she is an honest taxi driver (and doesn't go away from B at any time), then she can only travel North or East.
Let's consider her first decision. She can only go North or East, so 2 choices:
Now, looking at the first 4 city blocks, we see there are 6 choices:
Continuing, we find the following number of possible routes as we add more rows and columns of city blocks:
2 (for 1×1), 6 (for 2×2), 20 (for 3×3), 70 (for 4×4), ...
You may recognise these as being the middle number of each second row in Pascal's Triangle.
This is also connected with counting theory and we can show that for our 10×10 grid, our taxi driver will have
20C10 = 184,756 choices for getting from C to B.
An interesting question arises
Let's now take a route that gives us a more diagonal shape, as follows.
Once again, our total distance is going to be 2 km.
But for interest, let's imagine we can actually travel along lanes that pass in the middle of the city blocks as follows.
Our total distance is still 2 km.
But now let's push it even more, and take many tiny zig-zags as follows. Our total distance is still 2 km.
But what is the limit of this process? Won't we actually be smoothly travelling up the diagonal, since we can't even steer the car North then East, since the steps are too small?
And now we have the interesting question. What will be the distance the taxi travels up this smooth diagonal?
Well, √2, of course, from Pythagoras' Theorem. So the distance from C to B is no longer 2 km, but around 1.414 km, or 0.586 km less than 2 km!
Where did that 0.586 km go?
See the 18 Comments below.