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
(
dmoews@fastmail.fm )
To the puzzle;
to the puzzles list;
to the home page