Voy a recoger mis comentarios en una respuesta que se modifica la de John Hughes y Doug M. El resultado de todo esto es: La "prueba" clasifica los primos y las potencias de 2.
Como las otras dos respuestas se señaló, más de uno de los bordes de golpear dos bordes de tocar un vértice en la "prueba" es equivalente a: Hay $0 \le v \neq u \le n-1$ tal que
$S_v \equiv S_u$ mod $n$,
donde $S_i := \sum_{j=0}^i i= \displaystyle\frac{i(i+1)}{2}$.
Edit: es un poco más complicado: $S_u$ el número de un vértice significa que existen dos bordes de tocarlo, uno de longitud $u$ y uno de longitud $u+1$. Desde wlog $n>1$, en el caso de $u\neq 0$ hay exactamente dos, y si $u=0$, el intercambio de $u$ $v$ a ver que la siguiente consideración también se ocupa del caso. Existe una posibilidad (al lado de $u=v$) donde $S_u \equiv S_v$ mod $n$ es permitido, porque sin bordes aparecen en el gráfico: a Saber, cuando se $u \equiv -v-1$ mod $n$, o, equivalentemente, con nuestras desigualdades, $u+v+1=n$. Porque entonces el borde después de $v$ ("a $S_v \equiv S_u$") es una de las $u+1$-paso "se tira hacia atrás", y el siguiente es uno de los $u$-ésimo paso "se tira hacia atrás". En realidad, esto no sucede para todos los impares $n$, primos o no. Para "Pasar la prueba", es decir, no más de dos bordes de tocar cada vértice se traduce en la "Si $S_u \equiv S_v$ mod $n$, entonces cualquiera de las $u=v$ o $u+v+1=n$". Esto no cambia el resultado de la siguiente, aunque.
Observe que después de $n$ pasos, no hay periodicidad debido a que, por $0 \le k\le n-1$, (como Doug M notas) $S_{n+k} \equiv S_{n-k-1}$ mod $n$, y más en general, pero básicamente con el mismo cálculo $S_{rn+k} \equiv S_{rn-k-1}$ mod $n$. Gráficamente esto significa que siempre que eventualmente moverse hacia atrás y adelante en el gráfico que apareció después de su primera $n-1$ pasos.
La proposición: Un número $n$ pasa la prueba (es decir, no hay "múltiples éxito" aparece en el gráfico) si y sólo si $n$ es un primo o una potencia de $2$. (Por lo de los números primos y 4,8,16,32 ... pasar la prueba, pero hay otros números).
Prueba: Primer aviso de que si $u-v=1$ $S_u-S_v=u \not\equiv 0$ mod $n$, para el caso de $u-v=1$ no puede ocurrir.
Ver que el primer $n$ pasa la prueba, ver tanto citado respuestas (más que de la observación).
Editar ... y se nota que la única posibilidad que queda es $u+v+1=n$, lo que, como se dijo, todavía pasa la prueba.
A ver que $n=2^k$, $k\ge 2$, pasa la prueba, asumir tuvimos $u,v$ anterior. A continuación, como en John Hughes respuesta se deduce que $(u+v+1)(u−v)=0$ mod $n=2^{k}$, y porque sabemos $u-v \neq 1$, pero también se $u-v <2^k$ por nuestro asumido las desigualdades, el factor de $u-v$ contiene una potencia de 2 mayor que 1 y menor que $k$, por lo que el otro factor $u+v+1$ debe contener algunos potencia de 2. Pero ambos factores tendría que ser, que no puede ser: Si $u-v$ es incluso, $u$ $v$ tiene la misma paridad que hace que $u+v+1$ impar.
Ahora a la inversa, es decir, todos los demás números de fallar la prueba:
La primera (la más fácil) , $n$ es un extraño número compuesto. Observar que, a continuación, $2$ es invertible mod $n$. Escribir $n=a\cdot b$$1<a,b<n$. Elegir a los representantes de $u=(a+b−1)/2$, $v=(a−b−1)/2$ mod $n$ (observar que $u-v \equiv b$ mod $n$): Se va a hacer el truco, como el cálculo de John Hughes respuesta es completamente reversible modulo $n$, incluyendo la división por 2.
Edit: También, $u+v+1 \equiv a \not\equiv n$ mod $n$.
Ejemplo: $n=15=3\cdot 5$. El inverso de 2 modulo 15 es de 8, por lo que podemos establecer $u=(3+5-1)\cdot 8 \equiv 11$ mod $15$ $v=(3-5-1)\cdot 8=-24 \equiv 6$ mod $15$, y se puede comprobar que el mismo vértice es hit "desde diferentes direcciones" en el paso 6 y 11. (O, $S_6=21 \equiv S_{11}=66 \equiv 6$ mod $15$.)
Otro ejemplo: $n=21 = 3\cdot 7$. El inverso de 2 modulo 21 es de 11, así que nos pusimos $u=(3+7-1)\cdot 11 \equiv 15$ mod $21$ $v=(3-7-1)\cdot 11 \equiv 8$ mod $21$. Si usted entró en la imagen, se observa que el vértice en el paso 8 se vuelve a golpear de diferentes direcciones en el paso 15. (Yo no estoy diciendo que el método se encuentra cada varios de golpe, y ya hay uno en los pasos 5 y 8 como nota.)
Segundo caso, $n$ es, incluso, pero no un poder de $2$. Por lo $n=2^k m$ $k\ge 1$ $m >1$ impar.
Tenemos que ser cuidadosos acerca de potencias de 2 y consiguiendo $u$ $v$ $0$ $n-1$ ahora, porque la fórmula $\frac{u(u+1)}{2}$ no está bien definida para $u \in \mathbb{Z}/n$.
Si $2^{k+1}-m-1 \ge 0$, podemos establecer$u=\frac{1}{2}(2^{k+1}+m−1)$$v=\frac{1}{2}(2^{k+1}−m−1)$. Se verifica que $u$ $v$ se encuentran entre el $0$ $n-1$ ($u\le n-1$ es tal vez el más difícil de demostrar, pero factible). Un poco de computación con el teorema del binomio y de mantenimiento de la pista de la derecha potencias de 2 se muestra que el $\frac{u(u+1)}{2}=\frac{v(v+1)}2$ mod $n$. Además, es fácil ver que $u-v \equiv m \not\equiv 0$ mod $n$.
Edit: Y $u+v+1=2^{k+1} \neq n$.
Así que tenemos un verdadero, visible doble golpe con al menos cuatro distintas aristas de tocar el vértice.
Ejemplo: $n=20= 2^2\cdot5$ da $u=6$, $v=1$ que es un doble golpe en su imagen, aunque no se marca en rojo.
Si $2^{k+1}-m-1 < 0$, elija $r >1$ mínima tal que $2^{k+r}-m-1 \ge 0$. (En otras palabras, $m+1 \le 2^{k+r}\le 2m+2$). A continuación, establezca $u=\frac{1}{2}(2^{k+r}+m−1)$$v=\frac{1}{2}(2^{k+r}−m−1)$. Básicamente el mismo cálculo como antes de la muestra $\frac{u(u+1)}{2}=\frac{v(v+1)}2$ mod $n$. De nuevo $u-v \equiv m \not\equiv 0$ mod $n$, y las desigualdades asegúrese de que (... skip pequeño y desagradable cálculos ...) que $u$ $v$ se encuentran entre el $0$$n-1$.
Edit: Como bien como $u+v+1=2^{k+r} \neq n$.
Ejemplo: $n=26 =2\cdot 13$ da $r=3$, $u=14$ y $v=1$. Comprueba por ti mismo que en un 26-gon, el mismo vértice es golpeado después de 1 y 14 pasos. (O observar que $105=S_{14} \equiv 1=S_1$ mod 26, es el primer vértice tocado por un borde de longitud 1 ("ir"), uno de longitud 2("salir"), uno de longitud 14 ("ir") y uno de longitud 15 ("salir"). Tal vez hay incluso más).
