What do you mean by "The route can be frequented in both directions"???? I am confused!!!!

By "The route can be frequented in both directions", it is meant that there are no one-way-sections, i.e. if $A$ and $B$ are two neighboured bus stops, the bus can drive from $A$ to $B$ as well as from $B$ to $A$.

Do you mean that the bus-stops for the opposite routes are different??? If not there is no route!!! Because there are not n+2 sections without a common bus-stop!! Please reply quick!!!

As an example suppose n=3: We have stops 0,1,2 (0 is Zurich). A possible route is then: 0--1--2--0--1--0 Two routes are considered equal if and only if they are the same sequence of stops. Anyway it is easy to see that this is equivalent to asking how many $(a_1,a_2...a_{n+2}) \in \{1,-1\}^{n+2}$ there are such that: $a_1+a_2...+a_{n+2} \equiv 0 \mod n$ Which can be easily done with some casework.

RSM wrote: Do you mean that the bus-stops for the opposite routes are different??? If not there is no route!!! Because there are not n+2 sections without a common bus-stop!! Please reply quick!!! I don't really know what you mean now...why should we need $n+2$ sections with a common stop? I only said that "if $A$ and $B$ are two neighboured bus stops, the bus can drive from $A$ to $B$ as well as from $B$ to $A$.", which does really mean that the bus can drive in both directions, and not if it drives from $A$ to $B$, it must drive back from $B$ to $A$, too - or whatever you understood... kamil9876 wrote: Anyway it is easy to see that this is equivalent to asking how many $(a_1,a_2...a_{n+2}) \in \{1,-1\}^{n+2}$ there are such that: $a_1+a_2...+a_{n+2} \equiv 0 \mod n$ Which can be easily done with some casework. Why is this equivalent? Did you consider that the bus has to stop at all the bus stops?

It seems very easy (or do I miss something?) There are $2n$ possible routes. Each route consists "essentially" of going around the $n$ segments from Z to Z after having chosen one of both directions. Two segments are still left to do, so at exactly one town T, it goes back to the previous and again to T before resuming the sircle. So with Zürich=0 and numbers $\pmod n$, for each $k=1,...,n$, there is a route $0,1,2,...,k,k-1,k,k+1,...n$ and a route $0,-1,-2,...,-k,-k+1,-k,-k-1,...-n$.

Martin N. wrote: Given is a circular bus route with $n\geqslant2$ bus stops. The route can be frequented in both directions. The way between two stops is called section and one of the bus stops is called Zürich. A bus shall start at Zürich, pass through all the bus stops exactly once and drive along exactly $n+2$ sections before it returns to Zürich in the end. Assuming that the bus can chance directions at each bus stop, how many possible routes are there? The big issue is with the statement (presumably a not perfect translation from the German original). The statements "pass through all the bus stops exactly once" and "drive along exactly $n+2$ sections before it returns to Zürich in the end" are contradictory, if we assume that as the bus passes from one section to another, even without stopping at the bus stop, it actually passes through that stop. I think the first was meant to say "stop at each of the bus stops exactly once"; this will remedy the inconsistency. Now another question arises: can the bus change directions at a bus stop without actually stopping at that bus stop (one would think, no, since it's difficult, and dangerous, to reverse course without stopping). As an example, for $n=2$, with bus stops $Z$(ürich) and $A$(ltdorf), one possible such route with $n+2$ sections is $Z(AZ)AZ$, where the bus goes from $Z$ towards $A$ (let's say clockwise), passes through $A$ without stopping, continues to $Z$, passes through $Z$ without stopping, reaches again $A$, where it stops, then it returns to $Z$ (one way or another) and rests there. Aside question: when passing through $A$ the first time atound, without stopping there, can the bus change directions on its way back towards Zürich? Is that what was meant?

Thank you mavropnevma for pointing out my mistake - the problem statement was definitely wrong here, I'm sorry for being unprecise... But I corrected it now; what is meant is that the bus stops at each bus stop at least once - and the terms "stop" and "pass through" are used equivalently. spanferkel wrote: It seems very easy (or do I miss something?) There are $2n$ possible routes. Each route consists "essentially" of going around the $n$ segments from Z to Z after having chosen one of both directions. Two segments are still left to do, so at exactly one town T, it goes back to the previous and again to T before resuming the circle. So with Zürich=0 and numbers $\pmod n$, for each $k=1,...,n$, there is a route $0,1,2,...,k,k-1,k,k+1,...n$ and a route $0,-1,-2,...,-k,-k+1,-k,-k-1,...-n$. Well, you are basically right - but you miss two things: a) You can do step backwards at $n+2$ stops - your $k$ can range from $0$ to $n+1$! b) There is some casework to do - for small $n$, the route does not necessarily have to be a circle.

Since we have to cross no less than $n$ sections in order to cover each bus stop (by going in perfect circle), we need to make $1$ extra round trip between any two consecutive bus stops, or in other words we need to traverse back and forth on exactly $1$ of the given $n$ sections, which making the circular trip starting from Zurich. Now, consider the $n-2$ sections which are not adjacent to Zurich, since we have to consider both clockwise trip as well as counterclock wise trip, we have $2$ ways in which any of these $n-2$ sections can be traversed back and forth. Finally, the sections adjacent to Zurich can be traversed back and forth in $4$ different routes depending on when you tranverse the section second time (either after completing the full circle or before) So total number of routes = $2(n-2) + 2*4 = 2*(n+2) $