Caminatas de "Robot" no auto-intersectantes

Question

Pregunta 208 en Project Euler describe los recorridos de "robots" que se mueven en partes de un arco circular:

Un [$5$-]robot se mueve en una serie de arcos circulares de un quinto (72°), con la libertad de elegir un arco en sentido horario o antihorario en cada paso, pero sin girar en el sitio.

Sea un robot $n$-robot un robot que se mueve en $1/n$ de un arco circular.

Sea un camino $(i, j)$ un camino que consiste en $i$ pasos en sentido horario, seguidos por $j$ pasos en sentido antihorario, seguidos por $i$ pasos en sentido horario, y así sucesivamente.

---

La siguiente imagen muestra los caminos $(i,j)$ para todos los $0 < i < j < 5$ de un $5$-robot. En orden, estos son: un camino $(1, 2)$, un camino $(1, 3)$, un camino $(1, 4)$, un camino $(2, 3)$, un camino $(2, 4)$, y un camino $(3, 4)$.

Es claro en la imagen que los caminos $(1, 2)$, $(2, 3)$, y $(3,4)$ no se cruzan.

Si deseas probar por ti mismo, puedes hacerlo en esta aplicación web. En particular, puedes cambiar n=5 y w=1,4 en la URL por el valor de $n>2$ que desees.

---

Datos

Aquí hay algunos datos para caminos $(i,j)$ para un $n$-robot con $3 \leq n \leq 12$ y $1 \leq i < j < n$.

---

Pregunta

En general, ¿existe alguna regla combinatoria que determine si un camino $(i, j)$ no se cruza para un $n$-robot? ¿En caso afirmativo, predice cuántas intersecciones habrá?

---

Conjetura

Supongamos que $i < j < n$. Entonces un camino $(i,j)$ no se cruza si y solo si $(j-i) \mid n$ y $6j < 5n$.

Answer 1

Pido disculpas por la falta de formalidad. Este argumento no es fácil de armar. Pero esperemos que dé suficiente intuición para convencer.

Para el siguiente argumento, asumimos que todos los caminos son trazados por un $n$-robot.

Probamos que un camino $(i,j)$ no se intersecará consigo mismo si y solo si $j-i\mid n$ y $6j<5n$. Esto requerirá dos observaciones, cuyas demostraciones esbozaremos (de todas formas, estos resultados deben sentirse intuitivos).

---

Observación 1: Un camino $(i,j)$ tiene ejes de simetría a través de los puntos medios de sus arcos componentes.

Esquema de la demostración: Simplemente podemos notar que la construcción de nuestros caminos es completamente simétrica con respecto a estos ejes.

Observación 2: Un camino $(i,j)$ tiene un número de giros de $\frac{j-i}{\gcd(n,\,j-i)}$ (y en particular es cerrado).

Esquema de la demostración: Simplemente llevamos un seguimiento de la suma de nuestros vectores de desplazamiento en cada paso. Solo pueden cancelarse cuando cada uno de los posibles se ha utilizado la misma cantidad de veces. Es fácil demostrar que esto sucederá por primera vez después de $\text{lcm}(n,\,j-i)$ pasos, lo que inmediatamente nos da el número de giros.

---

Claramente, para que nuestro camino no se auto-intersecte, su número de giros debe ser igual a $1$. Por la observación $2$, esto implica $j-i\mid n$. Además, por la observación $1$, podemos generar fácilmente una región fundamental para las simetrías rotacionales del camino. Debería verse así.

La mitad superior abarca $\frac{j}{n}$ de un círculo, las mitades inferiores abarcan cada una $\frac{i}{2n}$.

La única forma en que estas regiones fundamentales podrían combinarse para crear una forma auto-intersectante sería si las regiones fundamentales en sí mismas se auto-intersectaran. Pero esto solo sucede cuando $\frac{j}{n}\geq\frac{5}{6}$, cuando los círculos (completados) que componen el camino se tocan o se intersecan. (Recuerda que tres círculos tangentes crean arcos mayores de $\frac{5}{6}\cdot2\pi$). Y de igual manera, al usar esto, es fácil ver que cuando $\frac{j}{n}\geq\frac{5}{6}$, el camino se auto-intersecta. Esto prueba nuestro resultado deseado. $\blacksquare$