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?

It became apparent that triangular numbers were in play here
but I was having trouble trying to derive a viable equation.
I found a reference where I recognised numbers from one of
my series embedded in Pascal's triangle!

My sets of series were in fact the diagonals of Pascal.

My table was created in a spreadsheet.  I copied "1" down
the "A" column and "1" across Row 12. In B11 I "Summed"
the values of B12 and A11.  I copied this cell's value upwards
and across the grid.  Then I began to look for something
that was repeated 4 times, was under 10,000 and in the
top-right quadrant. 

I was a little intrigued by some of the neighbours,
zeroes in both the "H" and "T" place.

1 12 78 364 1365 4368 12376 31824 75582 167960 352716
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

Edited on December 4, 2007, 7:23 pm

Posted by brianjn on 2007-12-04 18:05:12