Results 1 to 14 of 14

Thread: Shortest route question

  1. #1
    Super Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    665
    Thanks
    4

    Shortest route question

    I added a file.
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    665
    Thanks
    4

    Re: Shortest route question

    Page 150.Question number 8.
    Mr X is living in a district. He can only go east or South.In how many ways he can go from A to B?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    665
    Thanks
    4

    Re: Shortest route question

    Shortest route  question-ads-z.png

    Mr X is living in a district. He can only go east or South.In how many ways he can go from A to B?

    Original question is in Page 150. 8th question.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    665
    Thanks
    4

    Re: Shortest route question

    4!/3!+4!/2!.2!+4!/3!.3!/2!

    My work is this but according to my book the answer is 23.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    19,024
    Thanks
    2763

    Re: Shortest route question

    There is no picture with question 6. And the picture in your last post is from problem 8. Where are A and B.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    665
    Thanks
    4

    Re: Shortest route question

    Page 150 and question 8.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    665
    Thanks
    4

    Re: Shortest route question

    I tried to draw the figure with paint. In the book it is better. I uploaded an Adobe file. There are 7 grids in the picture but I couldn't draw well but I also uploaded the book.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    665
    Thanks
    4

    Re: Shortest route question

    We had solved the 7 th question before. This one is the 8 th.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,381
    Thanks
    902

    Re: Shortest route question

    Any path from A to B can be written as a string of seven characters where each character is either E or S. There are exactly 3 S's and 4 E's. But, there are several forbidden paths. The first forbidden path is if you go SS. How many ways are there to get to B if you start with SS? Well, you need 4 E's and one S more. So, there are $\dbinom{5}{1}$ forbidden paths that begin with SS. Next, EEE is a forbidden path. There are $\dbinom{4}{1}$ different forbidden paths that start with EEE. Finally, the path that ends with SS is forbidden. There are $\dbinom{5}{1}$ forbidden paths that end with SS. However, this double counts paths that both begin with EEE and end with SS. There are two paths that are double counted: EEEESSS and EEESESS, so we need to add back in two.

    So, there are $\dbinom{7}{3}-\dbinom{5}{1}-\dbinom{4}{1}-\dbinom{5}{1} +2 = 23$
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    665
    Thanks
    4

    Re: Shortest route question

    How did you get (5,1) forbidden paths that end with SS? I go EEE and I just see SSS.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,381
    Thanks
    902

    Re: Shortest route question

    To find a forbidden path, find an intersection that is not available. In this case, I chose the intersection that is North two from B. Here are all paths that end with SS (go through the intersection two north of B, which cannot be reached):

    EEEESSS
    EEESESS
    EESEESS
    ESEEESS
    SEEEESS

    In other words, I have five letters, S,E,E,E,E, and I find all permutations of those five letters. Once I choose where S goes, all other letters are E, so it is: $\dbinom{5}{1}$.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Nov 2010
    Posts
    2,381
    Thanks
    902

    Re: Shortest route question

    Technically, to Inclusion/Exclusion effectively, I should have enumerated all possible unavailable vertices. That would be:

    Let $P_*$ be the set of all paths (including ones that go through unavailable intersections)
    Let $P_1$ be the set of all paths that starts with SS (this takes you to an unavailable intersection two positions South of A)
    Let $P_2$ be the set of all paths that starts with SSS (this takes you to an unavailable intersection three positions South of A)
    Let $P_3$ be the set of all paths that start with EEE (this takes you to an unavailable intersection three positions East of A)
    Let $P_4$ be the set of all paths that start with EEEE (this takes you to an unavailable intersection four positions East of A)
    Let $P_5$ be the set of all paths that end with SS (this is all paths that go through an unavailable intersection two positions North of B)

    Let $[5] = \{1,2,3,4,5\}$

    Then by the Inclusion/Exclusion principle, the total number of paths is given by:

    $\displaystyle |P_*| + \sum_{A \subseteq [5]}(-1)^{|A|}\left|\bigcap_{n\in A} P_n\right|$

    However, since $P_2 \subsetneq P_1$ and $P_4\subsetneq P_3$, I simplified it.
    Last edited by SlipEternal; May 10th 2017 at 05:10 PM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    665
    Thanks
    4

    Re: Shortest route question

    A---+---+
    | | |
    +---+---D---+
    | | |
    C---+---E---+
    | | | |
    +---F....-+---B

    Every route must pass through C and D.

    A to C: 2 paths
    C to B: 4C3 = 4 paths
    A to B through C: 2*4 = 8 paths

    A to D: 3C2 = 3 paths
    D to E: 2C1 = 2 paths
    E to B: 2C1 = 2 paths
    D to B through E: 2*2=4 paths
    D to F: 1 path
    F to B: 1 path
    D to B through F: 1*1 = 1 path
    D to B: 4+1 = 5 paths
    A to B through D: 3*5 = 15 paths

    A to B: 8+15 = 23 paths
    Last edited by kastamonu; May 11th 2017 at 12:15 AM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Super Member
    Joined
    Oct 2012
    From
    Istanbul
    Posts
    665
    Thanks
    4

    Re: Shortest route question

    Many Thanks for your help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Quickest Route
    Posted in the Calculus Forum
    Replies: 3
    Last Post: Nov 30th 2010, 05:18 PM
  2. Square route question
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Jul 5th 2010, 12:45 PM
  3. minimum spanning tree/shortest route problem
    Posted in the Math Topics Forum
    Replies: 0
    Last Post: Jan 7th 2010, 02:30 AM
  4. shortest distance question
    Posted in the Calculus Forum
    Replies: 1
    Last Post: Apr 9th 2008, 03:23 AM
  5. Shortest distance question
    Posted in the Geometry Forum
    Replies: 6
    Last Post: Oct 5th 2006, 12:27 PM

/mathhelpforum @mathhelpforum