A mathematical worm starts from point $A$ and reaches point $B$ in the figure below.

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-04.jpg?height=426&width=436&top_left_y=453&top_left_x=772)

B

This mathematical worm always moves along the black lines in the drawing above, and never passes over a place it has already been to. Additionally, this worm can move down, up, and to the right, but not to the left. For example, a possible path for the mathematical worm to go from point $A$ to point $B$ could be:

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-04.jpg?height=420&width=419&top_left_y=1298&top_left_x=790)

a) In how many different ways can the mathematical worm go from point $A$ to point $B$ through paths contained in the segments shown in the figure below? (following the rules described above).

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-04.jpg?height=466&width=440&top_left_y=2020&top_left_x=751)

b) What is the total number of ways the mathematical worm can go from point $A$ to point $B$? (following the previous rules, for any path, not just those in part a)).
Solution

a) To make a path contained in the segments of the figure, the mathematical worm must choose, every two steps, one up and one to the right, or one to the right and one up. For example, if the worm takes the path illustrated below (in the thicker line)

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-24.jpg?height=565&width=645&top_left_y=1939&top_left_x=611)

it means that she chose to go to the right, then up; then chose to go up, then to the right; then chose again to go up, then to the right; then chose to go to the right, then up; then again to the right, then up; and, finally, chose to go up, then to the right. Since the worm had to make this choice six times, and each time she had two possibilities, the total number of paths she can take is:

$$
2 \times 2 \times 2 \times 2 \times 2 \times 2 = 64 \text{ paths. }
$$

b) Let's number the lines of the grid:

![](https://cdn.mathpix.com/cropped/2024_05_01_cc59d970f26105cc4ca1g-25.jpg?height=719&width=806&top_left_y=617&top_left_x=725)

To go from point $A$ to point $B$, since the worm does not move to the left, she must move six times to the right. Since the worm does not pass through the same place twice, it is enough to say on which lines the worm moved to the right to determine the entire path. For example, in the path above, the sequence of lines where the worm moved to the right is:

$1^{\underline{st}}$ line, $4^{\underline{th}}$ line, $3^{\underline{rd}}$ line, $2^{\underline{nd}}$ line, $6^{\underline{th}}$ line, $4^{\underline{th}}$ line.

Since there are seven lines in the grid, each time the worm moves to the right, she has seven choices for the line. Since there are six steps to the right, this gives a total of $7 \times 7 \times 7 \times 7 \times 7 \times 7 = 117649$ possible paths for the worm to go from point $A$ to point $B$.