# In how many ways can you travel from city A to city B

In how many ways can you travel from city $$A$$ to city $$B$$ (see figure) without visiting any city twice if

a) you choose the shortest route,

b) you want to visit all cities along the way (dots in the picture),

c) choose any route.

Ad a) I think that the shortest ways are the ones with $$10$$ cities along the way and the answer is $$11$$.

Ad b) There is only one route including all the cities.

Ad c) I do not know how to deal with this one.

• c) is probably $2^{10}$ Commented Nov 30, 2019 at 17:36
• Could you explain why it is so? What do you think about a) and b)? Commented Nov 30, 2019 at 17:41

For $$c$$ you can specify the path by choosing which vertical bars you traverse. You start from $$A$$ and go up if you have chosen to traverse the bar. Then you go right and at each stage you traverse the bar or not and go right again. There are $$11$$ to choose from and you must choose an odd number so you wind up at $$B$$. There are $$2^{10}$$ choices. One way to see that is that you can choose any combination of the first $$10$$ verticals, then whether you use the last one is determined by the requirement that you use an odd number.
• There are 11 vertical bars. You have no choice on the last one, but a choice on each of the first 10. So $2^{10}$. [Also check for 2 bars: 2 routeses; 3 bars, 4 routes.] Commented Nov 30, 2019 at 17:53
• Thank you. Now I understand that the answer is $2^{10}$ routes. What with a) and b)? Commented Nov 30, 2019 at 18:00