All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Ways of the Grid (Posted on 2007-12-04)
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?

 See The Solution Submitted by Charlie Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Answer Comment 4 of 4 |
The required number of different shortest routes to each of these intersections is 3003.
 Posted by K Sengupta on 2008-12-28 00:45:36

 Search: Search body:
Forums (0)