Enigma 1465 — To the far quarter

On a sheet of graph paper marked out in square cells, using its lines I picked out a square area, which I divided into four square quarters.

In considering the number of different ways using only the lines of the graphs paper in which I could take the shortest route from the top left-hand corner of my area to a corner of one or more of the cells, I found the same answer (six) for the corners reached by going down one cell and across five, or by going down five and across one, or by going down two and across two.

I have now found four corners that can all be reached from the top left-hand corner of my area by the same number of different shortest routes using only the lines of the graph paper. All four of these corners are either on the border of or inside the bottom right-hand quarter of my area.

If I tell you that the answer is less than 10,000, tell me how many different shortest routes there are to each of these corners.

The number of possible distinct paths across an m×n rectangle is given by the number of ways of choosing the m x–direction steps within the m + n total number of steps.

=

(m + n) C m

=

(m + n) ! m !   n !

We need to find four points: (m₁,n₁), (m₂,n₂), (m₃,n₃), (m₄,n₄) such that all values of m and n satisfy
      N ≤ m ≤ 2 N,     and     N ≤ n ≤ 2 N
         where 2 N is the size of the original square.

As the diagram is symmetrical about the top left to bottom right diagonal, the number of routes to (m,n) will be equal to the number of routes to (n,m). So perhaps there are only two points with two mirror images, but that presupposes that none of the points is on the diagonal (i.e. m = n ).

However, given that the number of points is even, if one point is on the diagonal, then there will be another on the diagonal. This would require that there are two different values of n, n₁ and n₂ for which:

2 n1 C n1

=

(2 n1) ! n1 ! 2

=

2 n2 C n2

=

(2 n2) ! n2 ! 2

This cannot be because

2 (n+1) C n+1

=

(2 n + 2) ! (n + 1) ! 2

=

(2 n) ! (2 n + 1) (2 n + 2) n ! 2 (n + 1)2

=

2 n C n

(2 n + 1) (2 n + 2) (n + 1)2

         I.E.   ^{2 n} C _n is a monotonically increasing function of n, because the factor at the right of the equation is always greater than 1.

So we are looking for two points (m₁,n₁), (m₂,n₂) on the same side of the diagonal, i.e. m₁ > n₁   and   m₂ > n₂