Merry-go-round problem

Question

The problem sounds like this:

There are $n$ seats on a merry- go-round. A boy takes $n$ rides. Between each ride, he moves clockwise a certain number of places to a new horse. Each time he moves a different number of places. Find all $n$ for which the boy ends up riding each horse.

So if there are $n$ horses, first the boy could move by one place then he could move by $n + 1$ places then by $2n + 1$ so on and so forth, until he moves $(n-2)n + 1$ places, in which case he'd would have been ridden each horse only one time and taken unique number of steps, which implies that all $n$'s satisfy given condition.

Is there something that I'm missing?

Thank you for your answers

Answer 1

It cannot be done when $n$ is odd: The boy makes $n-1$ moves of all lengths $1$, $2$, $\ldots$, $n-1$ in a certain order. This advances him by $$s:=\sum_{k=1}^{n-1}k={n-1\over2}\>n$$ horses in total. Since $s$ is divisible by $n$ this implies that after the last move (on his $n^{\rm th}$ ride) he sits again on the horse he began with.

Answer 2

If there is $n$ places and the boy takes $n$ rides then yes indeed there is an infinite number of ways he's had rode each horses at the end.

If we note $(u_k)_{k\in [1,n-1]}$ a sequence representing the number of places he moves each turn then there's an infinite number of such sequence that satisfies that he rode each horses. Your sequence $u_k = (k-1)n+1$ is one of them.

Answer 3

Christian Blatter has shown that it cannot be done if $n$ is odd. It remains to show that it can be done if $n$ is even.

One way to do this is to alternate the odd numbers $1,3,\dots,n-1$ in increasing order with the even numbers $2,4,\dots,n-2$ in decreasing order. The number of places the boy will move each time is given by the sequence $$1,n-2,3,n-4,\dots,n-(n-2),n-1$$ Note that this is the same as moving one place forward, two places backward, three places forward, four places backward, etc. The horses that the boy has used will always form an unbroken chain (i.e., no gaps), and the boy will always move from one end of the chain to the other end of the chain, extending the length of the chain by one horse.