2
$\begingroup$

These type of questions that ask the Number of Paths are relatively easy when it a ordered grid, However this one isn't:

image

How do I account for all the paths without counting. And when you are only allowed to move to the right or down.

This is part of a timed test so what would be the fastest way to do it?

$\endgroup$
  • 1
    $\begingroup$ Is it assumed you can only move in the right and/or down direction? $\endgroup$ – Bram28 Nov 29 '17 at 23:45
  • 2
    $\begingroup$ 'This is a timed test' ...; are you saying you are taking this test right now?!? $\endgroup$ – Bram28 Nov 29 '17 at 23:50
  • 1
    $\begingroup$ What are the constraints? Not visiting the same point more than once? Differentiating between paths only based on what intersections they visit? I'm assuming going from A to B is one of the constraints. $\endgroup$ – Emil Nov 30 '17 at 0:03
2
$\begingroup$

Start by labelling the A as 1 (since there is one way to start your path, at A).

Then go to all the points that are reachable from already labelled points. The number of ways of getting to those points is the sum of the labels of the adjacent points. Repeat until you have the number of ways of travelling to B and all nodes are labelled.

If you are able to go backwards and repeat points then a simple cycle will tell you there are infinitely many ways of making it through the maze.

If you can only go on edges once then. Look at Eulerian paths. You'll need to omit some edges.

If you can only go to nodes once then see Hamiltonian paths.

$\endgroup$
2
$\begingroup$

First of all, we can label the vertices from which there is more than one viable path to $B.$

labeling

Now we work in reverse from $B.$ The only labeled vertex from which we can get to $B$ directly is $L,$ and there are clearly $3$ ways to do so. Hence, we get

first round counting

We continue in the same way. The only vertex from which we can get directly to $L$ is $K,$ and $K$ can only get to either $L$ or a single unlabeled vertex, so there are $3+1=4$ ways to get from $K$ to $B.$

second round counting

Next, only $J$ allows us a direct path to $K,$ and we can also get to an unlabeled vertex, so there are $4+1=5$ ways to get from $J$ to $B.$

third round counting

Each of $E$ and $H$ connect directly to $J,$ and to exactly $1$ unlabeled vertex, so there are $5+1=6$ ways to get to $B$ from either of them.

fourth round counting

From $C,$ we can get directly to $E$ and $1$ unlabeled vertex, giving $6+1=7$ ways to get from $C$ to $B.$ From $G,$ we can get directly to $E$ and $2$ unlabeled vertices, giving us $6+2=8$ ways to get to $B$ from $G.$ We can also get to $E$ from $D,$ but we need to hold off on that, since we can also get to the (as yet unnumbered) vertex $F$ from there.

fifth round counting

Next, we can get directly from $F$ to $G$ and to $1$ unlabeled vertex, giving us $8+1=9$ ways to get from $F$ to $B.$

sixth round counting

Then, from $D,$ we can get directly to $E$ or $F,$ giving us $6+9=15$ ways to get from $D$ to $B.$

seventh round counting

Finally, from $A,$ we can get directly to $C$ and $D,$ giving us $7+15=22$ ways to get from $A$ to $B.$

$\endgroup$
  • $\begingroup$ Very simple and easy to understand, but because I saw Stuart Stevens first I had to give him the answered... $\endgroup$ – The Math Guy Dec 1 '17 at 0:19
  • $\begingroup$ Of course! That's what I'd have done in your place. Unfortunately for me, I didn't see Stuart's answer until after I posted mine. :-p $\endgroup$ – Cameron Buie Dec 1 '17 at 1:55
  • $\begingroup$ Feel free to give me an "upvote" (if you haven't already done so). Also, welcome to Math.SE! $\endgroup$ – Cameron Buie Dec 1 '17 at 1:56
  • $\begingroup$ I already did give you an upvote... Thank You $\endgroup$ – The Math Guy Dec 1 '17 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.