### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,115)
- misc (2)
- project euler (2)
- puzzle (29)
- site news (43)
- tantalizer (29)
- teaser (3)

### Site Stats

- 166,357 hits

Programming Enigma Puzzles

5 February 2013

Posted by on **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

%d bloggers like this:

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.

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.