# Thread: Shortest route question

1. ## Shortest route question

I added a file.

2. ## 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?

3. ## Re: Shortest route question

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.

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.

5. ## 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.

6. ## Re: Shortest route question

Page 150 and question 8.

7. ## 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.

8. ## Re: Shortest route question

We had solved the 7 th question before. This one is the 8 th.

9. ## 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$

10. ## Re: Shortest route question

How did you get (5,1) forbidden paths that end with SS? I go EEE and I just see SSS.

11. ## 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}$.

12. ## 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.

13. ## 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

14. ## Re: Shortest route question

Many Thanks for your help.