Number of tourist paths

Question

Please, would someone give me a hint to this exercise?

Tourist path is refracted line from point (0,0) to (2n,0), created from 2n line segments, where every line segment is determined by vector (1,1) or (1,-1). Show that number of paths, which doesn't go under axis x, is same as number of paths which only just one line segment goes under the axis x

Answer 1

First, I think that your last bit of sentence "which only just one line segment goes under the axis x" should be "which only just two line segment goes under the axis x".

Second, just note that if there are only two segments under axis x (say that the crossings of the axis occur at $x=L$ and $x=L+2$ with $L<2n$), you are left with two similar problems :

• "On the left", from $x=0$ to $x=L$, how many paths can you find that do not cross the axis ?
• "On the right", from $x=L+2$ to $x=2n$ how many paths can you find that do not cross the axis ?

Now, you should also ask yourself how many $L$ exist such that only two segments go under the axis.

So basically, the whole problem reduces to know how many paths exist that never cross the axis.