Number of ways to ride from one city to another

75 Views Asked by At

I stucked with some combinatorial problem:

There are 3 highroads between city A and city B. Highroads are intersected with 4 countryroads. What is the number of ways to make a tour from A to B, if we can't ride in direction of A and can't ride twice through same part of road?

Official answer is $3^5=243$, because "we have three choices in 5 points of tour". I can't see why is this true. For middle highroad - yes, we can turn left,right or go forward, but if we are on upper highroad we can go only forward or right, and on lower highroad we can only go forward or turn left. Could anyone help me to see, what is wrong in my reasoning?

enter image description here

2

There are 2 best solutions below

0
On BEST ANSWER

The reason you are wrong is the following:

If you are on the top highway, yes you can only go forward or right, but if you go right you don't have to necessarily turn on the middle road.

If you are on the top you could go forward, right and turn on the middle OR right and turn on the bottom.

It is easier to think about choosing the 5 in between pieces: the first highroad, second and so on. For each choice you can uniquely connect them with country roads.

0
On

I don't think there's anything wrong with your reasoning; I think it's a perfectly reasonable response to the way the answer has been explained. It wasn't immediately clear to me either what they meant by having "three choices in 5 points of [the] tour."

What they mean is that in getting from A to B, you're going to take $5$ steps I'll call horizontal, interspersed with (or without) some vertical steps. The point is, you can plan in advance, for each horizontal step, whether it'll be on the high, middle, or low road, which is the $3^5=243$ choices; whatever you choose then dictates the vertical steps.

In short, this is a problem where if you try to do the counting in a "straightforward" manner, where you consider the number of choices along the way, you get a complicated, branching tree of possibilities, but if you look at it in the right way it becomes very simple.