Any shortest path from A to B must go right 7 times and up 6 times. If there were no large (2x2) blocks present, a shortest path could order these subpaths in any order, and there would be C(13,7) = 13!/(6! 7!) = 1716 of them. As it is, we have to subtract off those paths which go through the center of 2x2 blocks and thus cannot be made on our map. Consider, for example, the shortest paths through C, the center of the bottom 2x2 block. Such a path must first go right 3 times and up twice to reach C from A and then go right 4 times and up 4 times to reach B from C. Hence there are C(5,2)*C(8,4) = 5!/(3! 2!) * 8!/(4! 4!) = 700 such paths. Similarly, there are C(7,2)*C(6,1) = 126 paths through D, the center of the upper left 2x2 block, and C(10,4)*C(3,2) = 630 paths through E, the center of the upper right 2x2 block. Subtracting all these numbers off yields 1716 - 700 - 630 - 126 = 260 paths. For the final answer we must add back the paths that go through both C and E, since we subtracted such paths off twice: there are C(5,2)*C(5,2)*C(3,2) = 300 such paths, so we end up with 560 paths.

David Moews ( )

To the puzzle; to the puzzles list; to the home page