Un problema de conteo de atravesar un arreglo circular

Question

Vamos a no ser $n$ sillas, $C_1,C_2,\ldots,C_n$ alrededor de una mesa circular. Un gato comienza a saltar de $C_1$ y después del primer salto llega a $C_3$, después de que el segundo salto se alcanza a $C_6$ y así sucesivamente. Que es en el $k$th saltar el gato salta $k$ sillas. Ahora mi pregunta:

¿Hay un límite en el número de saltos (dependiendo $n$) o un número exacto de los saltos de tal manera que el gato visitas a todas las sillas de al menos una vez?

N. B me han demostrado que si $n$ es impar entonces no va a ser al menos un presidente que no va a ser visitado nunca. Por lo tanto $n$ debe ser par. También hay casos incluso de $n$'s de tal forma que algunas sillas no va a ser visitado nunca. Por lo tanto estoy buscando un límite en el número mínimo de saltos, donde el escenario es factible para algunos, incluso,$n$.

Answer 1

El gato de las mociones que se repita todos los $2n$ salta. Modulo $n$ el gato se mueve hacia adelante por un asiento más por saltar, por lo que las visitas de todos los asientos iff triangular en el que los números son un completo residuo sistema modulo $n$, que por esta pregunta pasa iff $n$ es una potencia de dos.

A continuación, el gato siempre tiene $2n-2$ salta a visitar cada asiento. Volver a numerar los asientos, por lo que el gato se inicia en el asiento 0 y escribir los números de los asientos del gato visitas en un bucle ($n=8$ a continuación):

 >2516433v
(0)      4
 ^7702516<

Después de cualquier $n$ saltos consecutivos cubriendo $\frac{n(n-1)}2\equiv n/2\bmod n$ espacios: el gato está en el lado opuesto de la mesa. Desde todos los asientos son visitados, cada residuo modulo $n$ aparece exactamente dos veces en el bucle. Sin embargo, la ampliación de los saltos hacia atrás nos encontramos con que $n-1$ sólo aparece en los dos lugares antes de que el 0 inicial, avanzando así el gato

• toma $2n-2$ salta antes de aterrizar en el asiento $n-1$,
• luego salta en el lugar y
• finalmente salta hacia adelante del asiento 0.

Todos los demás asientos aparecer dos veces en la primera $2n-2$ saltos, por lo $2n-2$ es la respuesta.