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

Home > Numbers
Ways of the Grid (Posted on 2007-12-04) Difficulty: 3 of 5
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.)
Solution No Subject | Comment 3 of 4 |

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

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information