# Find the number of paths for a person to reach the center of a garden

Here is a problem that is in the shortlist for Regional Math Olympiad in India, 2023. No solution is available online yet.

Assume a person is standing at point $$A$$ in a $$4-$$leveled circular park $$(\text{green circles}\{ABC, LDI, KEH, JFG\})$$ as in the diagram.

He can go from the outer park to the inner through brown paths. His main goal is to reach the center of the garden (point $$O$$).

Note: He never retraces any of the paths traveled by him. And brown path can only be used to travel inward (i.e. outer garden to inner one).

The task is to find the total ways he can reach $$O$$.

My approach:

I called the brown path between two consecutive circles a unit.

He must have traveled $$4$$ units.

The total ways of selecting these are $$16 \choose 4$$. However, there aren't the same ways for each selection of 4 units. For example, directly from $$C$$ to $$O$$, there are $$2^4$$ different ways. But $$C$$ to $$A$$ and directly to $$O$$ has $$2^3$$ cases.

Now I am stuck here as we can't simply multiply a number by total selection of units. It seems there is no other way rather than counting.

How can I solve this? And what if the person started from $$M$$, where $$M$$ is between $$A$$ and $$C$$.

• Note that "He must have traveled 4 units" need not be true. He could take ADLBCIHGO, so the brown distance is 6 units. Feb 13, 2023 at 20:42
• @CalvinLin sorry I forget to wrote about that. Feb 13, 2023 at 20:51
• This can be done recursively. The key is to think of it in terms of the number of paths there are from one node of a circle to any node of the next circle in. Is this number different for different circles? Feb 14, 2023 at 3:09

Notice that to get to the center the person has to take a total of four steps down (call these d.) So every path would have to contain d d d d; however, the person can choose to take some steps before each d.

At A, the person can choose to go directly down to D, or choose to go left (to B) or right (to C) before going down. If they go left, they can do so up to three times, but they cannot change direction and then go right as that would be retracing a path; by the same reasoning, they can go right up to three times but then they cannot go left. Thus, at A, there are seven left/right options available before going down: no steps, l, l l, l l l, r, r r, and r r r. These same options would repeat at each of the four layers.

So any path the person takes would look like

_ d _ d _ d _ d

where each blank can contain one of the seven options listed above.

Thus the number of paths starting from A would just be $$7^4$$.

If the person starts from M, the only difference is that they would not be able to take no left or right steps on the first level; the first blank would then only have six options, so the total number of paths starting from M would be $$6 \times 7^3$$.

Note: I realize the final step (to O) is not really "down" but that doesn't materially affect the answer.

• Nice one! And according to your solution, there will be $6×7^4$ ways if he starts from $M$. Feb 14, 2023 at 6:06
• @Anonymous Thanks for mentioning that, I'd forgotten about the second part of the question.
– A.J.
Feb 14, 2023 at 6:19
• I typed wrong that's $6×7^3$ . Feb 14, 2023 at 7:43