12 thoughts on “Shortest Path – 3

  1. Ratish, imagine that the region AKML is blocked off. Now if you have to go from A towards B you would have two options to start off, either via K or via L. Note also that you cannot visit K _and_ L and still manage a “shortest-path” route. So we can safely say “either K or L”. From the Fundamental principle of Counting (see https://crackthecat.wordpress.com/2013/03/25/the-fundamental-principle-of-counting/), we know that this means we can add up “number of ways via K” and “number of ways via L”

    Number of ways to get to K from A is just 1. So we need to only count ways from K to B, which require 11 steps, 6 horizontal and 5 vertical, which can be done (as in the previous post) in 11C5 ways. Similarly one can go from A to L in only one way, and from there onward to B in 11C3 ways (think about it!) hence we can say 11C5 + 11C3

    regards
    J

  2. For (g), the question should be “How many paths are there from A to B?” and not shortest path. This is because in order to reach B, starting from M will only give shortest way. Am I going wrong somewhere?

    • No, there could be “shortest paths” which do not pass through M at all (along the boundary of the rectangle, for example). And if I remove the shortest criterion there could be many many longer paths….

      regards
      J

Leave a Reply

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 )

Google+ photo

You are commenting using your Google+ 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 )

w

Connecting to %s