How to solve this kind of problems generally?

Question

How many paths are there from A to B which do not visit the same vertex twice?

(A) 8
(B) 16
(C) 20
(D) 24
(E) 32

Answer 1

Now here the number of ways to reach from A to point 1 are 4 which can be counted manually. Now from point 1 similarly there are 4 ways to reach point B. But these two cases are independent of each other hence by Multiplication rule in combinatorics we have number of paths from A to B in upper part as $4*4=16$.

Similarly in lower part there would be 16 of them.

Hence the answer would be $$16+16=32$$

Answer 2

Initially, let's count for the top-half only. Number of paths between $AC$ are $4$ i.e., $\implies APC,ApC,ApPC,APpC$.

There are a similar number of paths between $CB$. So, for each path between $AC$, there is path to $CB. $. So, total no. of paths are $4*4=16$.

There are identical no. in the bottom half.

So, total no.of paths are $16*2=32$

Answer 3

There are two global paths: north and south. Each global path is made of $4$ connected triangles. For each triangle there are two paths from one vertex to each of other two vertices. So the total number of paths: $$2×(2×2×2×2)=32.$$ That is, $2$ global paths times $4$ local paths of $2$ each.

Answer 4

In order to solve this kind of problem generally, look for constraints that let you divide the problem into simpler sub-problems.

The points $A$ and $B$ and the two midpoints of the top and bottom edges of the large square are "bottlenecks." The path can cross from one of the large triangular regions to another through one of these points, but it cannot return through that point.

This means if your first move is into the upper half of the figure, you cannot get into the lower half of the figure through $A,$ so the only way to get to $B$ is through the upper half of the figure. When you get to $B$ you have to stop (not go into the lower half of the figure), because if you leave $B$ you cannot come back (since that would be a second visit to $B$).

So you have to use either the upper half, or the lower half, but you cannot make any path that has points in both halves.

Also, once you reach the midpoint of the upper (or lower) half, you cannot go back to the part of the figure on the left.

This divides the problem into discrete sub-problems:

• How to choose the upper or lower half.
• How to get from $A$ to the midpoint.
• How to get from the midpoint to $B.$
• How solutions to all the other sub-problems combine into the solution of the whole problem.

Each of these sub-problems is much easier than the whole problem. Other answers show how this method applies to this particular problem.