0
$\begingroup$

the problem to solve is : How many routes are there from start to finish, only travelling from left to right?

I have a set of parallel lines with 7 triangles set inside. This creates 4 points across the top line and 5 lines across the bottom. the start point is at the bottom left and finish point at top right. (making only 8 of the 9 points usable..

enter image description here

I have concluded that there are 21 path ways to obtain this answer, but is there a formula to this question?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ $21$ is correct. As for a formula... try to argue why this is related to the Fibonacci sequence. $\endgroup$ – JMoravitz Apr 10 '20 at 2:37
  • $\begingroup$ JMoravitz , i understand Fibonacci sequence, but not sure how it fits here. I can see drawn out that the 1st triangle has 2 paths, 2nd triangle has 3 paths, 3rd triangle has 5 paths. I get stuck at this point $\endgroup$ – Jess Kaye Apr 10 '20 at 2:49
  • $\begingroup$ As a general technique in order to brute force the count for smaller examples, you can write down the number of paths possible to get from the start to each position, filling in the numbers beginning at the start, and recognizing that for later numbers that it is the sum of the numbers for the positions that feed into it. Once you've gone far enough in this particular example, it becomes clear that you are always adding two of the most recent numbers to get the next and they had fallen into the pattern of the Fibonacci sequence. $\endgroup$ – JMoravitz Apr 10 '20 at 2:52
  • $\begingroup$ There are other ways of course, for instance comparing this problem to other well known problems whose answer is the Fibonacci sequence, for instance tiling a $1\times n$ board with dominos and monominos, the comparison between the problems made by "squishing" the triangular grid so all points lie on the same line, what was a diagonal move counts as a monomino, and what was a move to the right counts as a domino, or by phrasing the argument in such a way that such a transformation isn't necessary as done below. $\endgroup$ – JMoravitz Apr 10 '20 at 2:56
  • $\begingroup$ @JMoravitz One way that I was thinking about it was "the number of ways to write $7$ as a composition consisting of $1$s and $2s$ (e.g. $7 = 1 + 2 + 2 + 2$), which are your monominos/dominos. But I then edited my answer to avoid this excursion since the explanation in the original setting is not too hard to explain. $\endgroup$ – angryavian Apr 10 '20 at 2:58
2
$\begingroup$

Number the vertices from left to right as $0,1,\ldots,8$ so that start is $0$ and finish is $7$.

Let $f(n)$ be the number of such paths from $0$ to $n$; we want $f(7)$. We have $f(0)=1$ and $f(1)=1$ automatically. We also have the recursion $$f(n) = f(n-1) + f(n-2)$$ because there are

  • $f(n-1)$ paths to $n$ that go through $n-1$, and
  • $f(n-2)$ paths to $n$ that do not go through $n-1$ (such paths must go through $n-2$, and then directly jump to $n$).

This yields the Fibonacci sequence, as JMoravitz noted in the comments. $$1, 1, 2, 3, 5, 8, 11, 21.$$

Improve this answer
$\endgroup$

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.