Enigmatic Code

Programming Enigma Puzzles

Enigma 1465: To the far quarter

From New Scientist #2626, 20th October 2007

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.

[enigma1465]

Advertisements

One response to “Enigma 1465: To the far quarter

  1. Jim Randell 5 February 2013 at 8:30 am

    This is a similar path counting problem to Enigma 1711, although in 2 dimensions rather than 3.

    The following Python code can either count the paths directly or use a formula to compute the number of paths. In either case it runs in 41ms.

    from itertools import count, product
    from collections import Counter
    from enigma import C, irange, cached, printf
    
    # considering shortest paths from (0, 0) to (x, y)
    
    # the shortest path requires x + y moves, and we can chose when to make
    # the moves in the x-direction (and the others are in the y-direction)
    def paths1(x, y):
      return C(x + y, x)
    
    # or we can just count them directly
    def paths2(x, y):
      if x == y == 0: return 1
      n = 0
      if x > 0: n += paths(x - 1, y)
      if y > 0: n += paths(x, y - 1)
      return n
    
    # chose whichever paths function you want
    paths = cached(paths2)
    
    # verify the example given
    assert paths(1, 5) == paths(2, 2) == paths(5, 1) == 6
    
    # consider a 2n x 2n square
    for n in count(1):
      n2 = n * 2
      # if there are more than 10,000 paths to (n, n) then there are
      # certainly more than 10,000 to any point in the far quarter
      if not paths(n, n) < 10000: break
      # find the number of paths to the possible points
      p = Counter()
      for (x, y) in product(irange(n, n2), repeat=2): p[paths(x, y)] += 1
      # and look for 4 (or more) points with the same number of paths
      for (k, v) in p.items():
        if v < 4 or not(k < 10000): continue
        printf("n2={n2} paths={k} points={v}")
    
    

    Solution: There are 3,003 shortest paths to the four points.

    The solution is found on a 10×10 square.

    If you remove the condition that the number of paths be less than 10,000 you find that the next lowest solution is on squares with sides 66, 68, 70, 72, 74, 76, 78 and there are 61,218,182,743,304,701,891,431,482,520 shortest paths.

    The next solution occurs on squares with sides 442 to 544, and there are 3,537,835,171,522,765,057,006,983,148,520,718,494,957,187,357,011,427,136,691,375,227,388,082,606,684,583,032,666,088,334,962,061,461,901,090,477,513,197,821,330,000,906,170,565,587,040,820,236,444,389,470,701,575,515,092,325,417,606,033,095,416,151,914,090,271,577,807,800 shortest paths.

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: