Start with a square grid cut from graph paper, say N x N. Mark the lower left intersection as the origin, so that the x and y coordinates each go from 0 to N. From the origin to any other intersection in the square there are a number of ways of traversing the grid lines to get there in the shortest possible path. For example, there are six ways of getting to (1,5) from the origin, and there are also six ways of getting to (5,1) and likewise for (2,2). So there are three intersections where the number of ways is six.

For a particular value of N, there are four intersections with the same number of ways to get there via a shortest path such that these intersections all occur within the top-right quarter of the square, or at least on its border. That is, all four have x≥N/2, y≥N/2. The number of ways in question is less than 10,000.

What is the number of different shortest routes to each of these intersections?

The number of distinct shortest routes from the origin (0,0) to (x,y) can be given by the expression (x + y)! / (x! * y!).  For a square grid 10 x 10, where both x >= N/2 and y >= N/2, there are 3003 distinct routes from the origin to intersections (5, 10), (6, 8), (8, 6), and (10, 5).

The next occurance of an N x N square grid where both x >= N/2 and y >= N/2 and where there are four intersections of equal shortest routes from the origin is the square grid 65 x 65 (these same four intersections are also available for square grids 66 x 66 through 78 x 78).  The intersections are (39, 65), (40, 63), (63, 40) and (65, 39) with each having 61218182743304701891431482520 distinct shortest routes.

Edited on December 4, 2007, 9:25 pm

Posted by Dej Mar on 2007-12-04 21:23:47