Question 208 on Project Euler describes walks of "robots" the move in parts of a circular arc:

A [$5$-]robot moves in a series of one-fifth circular arcs (72°), with a free choice of a clockwise or an anticlockwise arc for each step, but no turning on the spot.

Let an $n$-robot be a robot that moves in $1/n$ of a circular arc.

Let an $(i, j)$-path be a path that consists of $i$ clockwise steps, followed by $j$ anticlockwise steps, followed by $i$ clockwise steps, and so on.

The following picture shows $(i,j)$-paths for all $0 < i < j < 5$ of a $5$-robot. In order, these are: a $(1, 2)$-path, $(1, 3)$-path, $(1, 4)$-path, $(2, 3)$-path, $(2, 4)$-path, and a $(3, 4)$-path.

It is clear from the picture that the $(1, 2)$-path, $(2, 3)$-path, and $(3,4)$-path are non-self-intersecting.

If you want to play around for yourself, you can do so on this web app. In particular, you can change the n=5 and w=1,4 in the URL to whatever value of $n>2$ that you want.

Data

Here's some data for $(i,j)$-paths for an $n$-robot with $3 \leq n \leq 12$ and $1 \leq i < j < n$.

Question

In general, is there a combinatorial rule that will determine whether an $(i, j)$-path is non-self-intersecting for an $n$-robot? If so, does it predict how many intersections there will be?

Conjecture

Suppose that $i < j < n$. Then an $(i,j)$-path is non-self-intersecting if and only if $(j-i) \mid n$ and $6j < 5n$.

Solution 1:

I apologize for the lack of formality. This argument isn’t easy to piece together. But hopefully, this gives enough intuition to convince.

For the following argument, assume that all paths are traced by an $n$-robot.

We prove that an $(i,j)$-path will not intersect itself iff $j-i\mid n$ and $6j<5n$. This will require two observations, whose proofs we’ll sketch (these results should all feel intuitive, anyways).

Observation 1: An $(i,j)$-path has axes of symmetry through the midpoints of its component arcs.

Proof sketch: We can simply notice that the construction for our paths is completely symmetric with respect to these axes.

Observation 2: An $(i,j)$-path has a turning number of $\frac{j-i}{\gcd(n,\,j-i)}$ (and in particular is closed).

Proof sketch: We simply keep track of the sum of our displacement vectors at each step. They can only cancel out when each of the possible ones has been used the same amount of times. It’s easy to show that this will first happen after $\text{lcm}(n,\,j-i)$ steps, which immediately yields the turning number.

Clearly, for our path not to self-intersect, its turning number must be equal to $1$. By observation $2$, this implies $j-i\mid n$. Furthermore, by observation $1$, we can easily generate a fundamental region for the rotational symmetries of the path. It should look as follows.

The upper half spans $\frac{j}{n}$ of a circle, the lower halves each span $\frac{i}{2n}$.

The only way these fundamental regions could combine to create a self-intersecting shape would be if the fundamental regions themselves were self-intersecting. But this only happens when $\frac{j}{n}\geq\frac{5}{6}$, when the (completed) circles that make up the path are tangent or intersecting. (Recall that three tangent circles create major arcs of $\frac{5}{6}\cdot2\pi$). And likewise, by using this, it’s easy to see that when $\frac{j}{n}\geq\frac{5}{6}$, the path self-intersects. This proves our wanted result. $\blacksquare$