perplexus.info :: Numbers : Ways of the Grid

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?

Submitted by Charlie

Rating: 3.0000 (1 votes)

Solution: (Hide)

On a 10x10 grid there are 3003 ways of getting to (5,10), (6,8), (8,6) or (10,5).

1 11 66 286 1001 3003 8008 19448 43758 92378 184756 1 10 55 220 715 2002 5005 11440 24310 48620 92378 1 9 45 165 495 1287 3003 6435 12870 24310 43758 1 8 36 120 330 792 1716 3432 6435 11440 19448 1 7 28 84 210 462 924 1716 3003 5005 8008 1 6 21 56 126 252 462 792 1287 2002 3003 1 5 15 35 70 126 210 330 495 715 1001 1 4 10 20 35 56 84 120 165 220 286 1 3 6 10 15 21 28 36 45 55 66 1 2 3 4 5 6 7 8 9 10 11 1 1 1 1 1 1 1 1 1 1 1 Program to find the answer: DECLARE FUNCTION combi# (n#, r#) DEFDBL A-Z DIM num(500), numCt(500), numLow(500) CLS FOR x = 0 TO 20 FOR y = 0 TO x c = combi(x + y, x) did = 0 FOR i = 1 TO diffNums IF num(i) = c THEN IF y = x THEN numCt(i) = numCt(i) + 1: did = 1 ELSE numCt(i) = numCt(i) + 2: did = 1 END IF IF y < numLow(i) THEN numLow(i) = y END IF NEXT IF did = 0 THEN diffNums = diffNums + 1 num(diffNums) = c numLow(diffNums) = y IF y = x THEN numCt(diffNums) = 1 ELSE numCt(diffNums) = 2 END IF END IF NEXT y FOR i = 1 TO diffNums IF numCt(i) = 4 AND numLow(i) >= x / 2 THEN PRINT num(i), numCt(i), x, numLow(i) END IF NEXT NEXT x PRINT FUNCTION combi (n, r) IF r = 0 OR r = n THEN combi = 1: EXIT FUNCTION a = n: b = r: c = n - r comb = n / (b * c) DO a = a - 1: b = b - 1: c = c - 1 IF a > 1 THEN comb = comb * a IF b > 1 THEN comb = comb / b IF c > 1 THEN comb = comb / c LOOP UNTIL a < 2 combi = INT(comb + .5) END FUNCTION Addition to give the above table of values: FOR y = 10 TO 0 STEP -1 FOR x = 0 TO 10 c = combi(x + y, x) IF c < 1000000 THEN IF c = 3003 THEN COLOR 14: ELSE COLOR 7 PRINT USING \\"#######\\"; c; END IF NEXT PRINT NEXT PRINT Based on Enigma No. 1465 by Richard England, New Scientist, 20 October 2007.

Comments: ( You must be logged in to post comments.)

Subject	Author	Date
Answer	K Sengupta	2008-12-28 00:45:36
No Subject	Dej Mar	2007-12-04 21:23:47
Via a Spreadsheet	brianjn	2007-12-04 18:05:12
a solution	Dennis	2007-12-04 11:46:38

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (17)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info