Can You Escape the Infinite Loop?

Take a strip of paper $10$ inches long and $1$ inch wide, give it a single half twist, and join the two short edges to make a Möbius strip. Draw a dot on the midline of the strip, half an inch from both edges. Distance on the strip is measured as an ant crawls: the shortest path along the paper, which may pass over an edge onto the other face. Some point or points of the strip are as far as possible from the dot. How far?

The Fiddler, Zach Wissner-Gross, July 7, 2023(original post)

The official solution appeared in the post of July 14, 2023 and gives $5.05$ inches, attained at two points on the midline, and $N = 840$ for the Extra Credit, with an average of $195/14$ faces. Both agree with the answers below.

Solution

The ant walks on the paper’s surface, so a spot on the front of the paper and the spot directly behind it on the back are different places, joined only by walking round an edge. The dot is drawn on the front.

Unrolling the surface. Shortest paths on a flat surface are straight lines once the surface is laid out flat, and this one can be laid out completely. Put the front face in the plane as the rectangle $0 \le x \le 10$, $-\tfrac12 \le y \le \tfrac12$, with the dot at the origin. An ant walking over the top edge carries straight on, now on the back, and the back is a mirror image of the front across that edge, so it can be laid down as the next rectangle up, $\tfrac12 \le y \le \tfrac32$. Walking over the bottom edge works the same way, and so on, band after band. Walking $10$ inches along the strip brings the ant back to where it started on the paper, but the half twist has put it on the other face; that copy can be laid down as the next rectangle along. The whole plane is tiled by $10 \times 1$ rectangles, and moving one rectangle across or one up switches the face.

The figure shows the result. The shaded rectangles are copies of the back, the white ones copies of the front.

Where are the copies of the dot? A copy lies at $(10m, n)$ for whole numbers $m$ and $n$, provided the rectangle there is a front face, that is, provided $m + n$ is even. Moving one rectangle along also mirrors the strip top to bottom, but the dot sits on the midline, so its mirror image is itself. A path the ant crawls unrolls into a path in the plane of the same length, from the spot it ends at to one copy of the dot, and the shortest such path is straight. So the ant’s distance from the dot to a spot is the straight-line distance from the spot to the nearest copy of the dot.

The largest empty circle. So the question becomes: which point of the plane is farthest from its nearest black dot? Such a point is the centre of the largest circle that has no black dots inside it. Look at the three copies $O = (0, 0)$, $U = (10, 1)$ and $D = (10, -1)$. The point on the $x$-axis equidistant from all three is at $(c, 0)$ with $$c^2 \;=\; (10 - c)^2 + 1,$$ which simplifies to $20c = 101$, so $c = 101/20 = 5.05$. This is the centre of the circle through $O$, $U$ and $D$, and its radius is $5.05$. No other copy is closer to it: the next nearest are $(0, \pm 2)$, at a distance $\sqrt{5.05^2 + 4} \approx 5.43$, and $(20, 0)$, at $14.95$.

To see that no point does better, notice that the plane is covered by triangles like $OUD$ and their mirror images, such as $U$, $D$, $(20, 0)$, all with corners at copies of the dot. Each triangle has all its angles below $90^\circ$, so the centre of its circumcircle lies inside it. The lines from that centre to the midpoints of the three sides cut the triangle into six right triangles, each with corners at one dot, the midpoint of a side through that dot, and the centre. All three corners are within $5.05$ of that dot, and a disc contains every segment between its points, so the whole right triangle is too, with equality only at the centre. So every point of the plane is within $5.05$ of a copy of the dot. $$\boxed{\ \text{the farthest points are } 5.05 \text{ inches from the dot}. \ }$$ There are two of them. The centre $(5.05, 0)$ is on the front, on the midline $5.05$ inches along the strip; the centre of the mirror triangle, at $(-5.05, 0)$, is on the back, on the midline, $5.05$ inches the other way.

Three nearby guesses are each slightly wrong, which is what makes this puzzle treacherous. The point on the midline exactly halfway round is only $5$ inches away. The two points on the edge halfway round are $\sqrt{5^2 + 0.5^2} \approx 5.025$ inches away, since an ant can reach them along a straight line on the front. And on an untwisted ring the point opposite the dot on the inside would be $\sqrt{5^2 + 1^2} \approx 5.099$ inches away, but the twist opens a second, shorter route to it.

The computation

The check does not unroll anything. It covers both faces of the paper with a grid of spacing $\frac1{40}$ inch and lets the ant take short straight steps, with three rules for what happens when a step runs off the paper: over a long edge it lands on the other face, reflected; across the joined ends it lands on the other face with the strip turned over. Dijkstra’s shortest-path algorithm then finds the ant’s distance to every grid point. The steps run in $96$ directions, enough to follow straight lines closely, and they reproduce the paths in the figure exactly because $(198, 40) = 38\,(5,1) + 2\,(4,1)$.

import heapq
from math import gcd, hypot

# The strip is 10 by 1 in paper coordinates (x, y), with two
# faces, f = 0 (front) and f = 1 (back), on a grid of spacing
# 1/40. A step is a short straight move (di, dj) in grid units;
# land() says where it ends when it runs off the paper.
n = 40
X, Y = 10*n, n               # x in 0..X-1 (wraps), y in 0..Y

def land(i, j, f, di, dj):
    i, j = i + di, j + dj
    if j < 0:                # over the edge y = 0
        j, f = -j, 1 - f
    elif j > Y:              # over the edge y = 1
        j, f = 2*Y - j, 1 - f
    if i >= X or i < 0:      # across the join: the half twist
        i, j, f = i % X, Y - j, 1 - f    # flips y and face
    return i, j, f

steps = [(a, b) for a in range(-6, 7) for b in range(-6, 7)
         if (a, b) != (0, 0) and gcd(abs(a), abs(b)) == 1]

start = (0, Y//2, 0)         # the dot: midline, front face
dist = {start: 0.0}
heap = [(0.0, start)]
while heap:
    d, (i, j, f) = heapq.heappop(heap)
    if d > dist[(i, j, f)]:
        continue
    for a, b in steps:
        nxt = land(i, j, f, a, b)
        nd = d + hypot(a, b)/n
        if nd < dist.get(nxt, float("inf")):
            dist[nxt] = nd
            heapq.heappush(heap, (nd, nxt))

top = max(dist.values())
for (i, j, f), d in sorted(dist.items()):
    if d > top - 1e-9:
        print(f"farthest: x = {i/n:.3f}, y = {j/n:.3f}, "
              f"face {f}, distance {d:.4f}")

It prints

farthest: x = 4.950, y = 0.500, face 1, distance 5.0500
farthest: x = 5.050, y = 0.500, face 0, distance 5.0500

These are the two points found above: on the front $5.05$ inches along, and on the back at $x = 4.95$, which is $5.05$ inches back the other way.

Extra Credit

Now take a prism whose ends are regular $N$-gons, twist it by a random whole number of $N$ths of a turn (from one up to $N$, all equally likely), bend it into a loop and join the ends. For a square prism the twists of one, two, three and four quarters give $1$, $2$, $1$ and $4$ distinct faces, an average of $2$. For which $N \le 1000$ is the average number of distinct faces largest?

Solution

Number the prism’s side faces $0, 1, \dots, N - 1$ around the prism. Joining the ends with a twist of $k$ steps glues the end of face $i$ to the start of face $i + k$, counting modulo $N$. Following a single face round the loop over and over, you pass through faces $i$, $i + k$, $i + 2k$, and so on, and all of these are one face of the finished solid. Face $j$ is reached from face $i$ exactly when $j - i$ is a multiple of $k$ modulo $N$, and the multiples of $k$ modulo $N$ are exactly the multiples of $g = \gcd(k, N)$. So the faces fall into $g$ classes, and the twisted prism has $\gcd(k, N)$ distinct faces. The square prism’s $1, 2, 1, 4$ are $\gcd(1,4), \gcd(2,4), \gcd(3,4), \gcd(4,4)$.

The average over the $N$ twists is $$f(N) \;=\; \frac1N \sum_{k=1}^{N} \gcd(k, N).$$ It has a tidy form. For each divisor $d$ of $N$, the values of $k$ with $\gcd(k, N) = d$ are $d$ times the numbers from $1$ to $N/d$ that share no factor with $N/d$, and there are $\varphi(N/d)$ of those, where $\varphi$ is Euler’s totient function. So $$f(N) \;=\; \sum_{d \mid N} \frac{d\,\varphi(N/d)}{N} \;=\; \sum_{e \mid N} \frac{\varphi(e)}{e},$$ writing $e = N/d$. The last sum is multiplicative: it splits into a product over the prime powers in $N$. For a prime power, the divisors are $1, p, \dots, p^a$ and each $\varphi(p^j)/p^j$ with $j \ge 1$ equals $1 - 1/p$, so $$f(p^a) \;=\; 1 + a\Bigl(1 - \frac1p\Bigr), \qquad f(N) \;=\; \prod_{p^a \,\|\, N} \Bigl(1 + a\Bigl(1 - \frac1p\Bigr)\Bigr),$$ where $p^a \,\|\, N$ means $p^a$ is the exact power of $p$ dividing $N$.

Each prime contributes a factor between $1.5$ and $2$ for its first power, and each further power adds less than $1$ to that factor while multiplying the cost by $p$. So the winners are numbers built from many small primes, with small exponents. The search over $N \le 1000$ (below) settles it: the best is $840 = 2^3 \cdot 3 \cdot 5 \cdot 7$, with $$f(840) \;=\; \Bigl(1 + \tfrac32\Bigr)\Bigl(1 + \tfrac23\Bigr) \Bigl(1 + \tfrac45\Bigr)\Bigl(1 + \tfrac67\Bigr) \;=\; \frac52\cdot\frac53\cdot\frac95\cdot\frac{13}{7} \;=\; \frac{195}{14}.$$ $$\boxed{\ N = 840, \text{ averaging } \tfrac{195}{14} \approx 13.93 \text{ distinct faces}. \ }$$ The runners-up are well behind: $720 = 2^4 \cdot 3^2 \cdot 5$ averages $12.6$ and $900 = 2^2 \cdot 3^2 \cdot 5^2$ averages $12.13$. Adding the prime $7$ to $120$ multiplies the average by $13/7$, almost doubling it, which no alternative within $1000$ can match.

The computation

The check glues the faces directly. For each twist it joins face $i$ to face $i + k$ with a union–find structure and counts the classes, confirms the square prism’s $1, 2, 1, 4$, and confirms that the count equals $\gcd(k, N)$ for every twist of every prism up to $N = 60$. It then averages the face counts for every $N$ up to $1000$ and lists the three best.

from fractions import Fraction

def distinct_faces(N, k):
    """Join an N-gon prism's ends with a twist of k/N of a
    turn and count the faces. Once round the loop, side face
    i runs on into side face i + k (mod N)."""
    parent = list(range(N))
    def root(a):
        while parent[a] != a:
            a = parent[a]
        return a
    for i in range(N):
        parent[root(i)] = root((i + k) % N)
    return len({root(i) for i in range(N)})

square = [distinct_faces(4, k) for k in (1, 2, 3, 4)]
assert square == [1, 2, 1, 4]
assert all(distinct_faces(N, k) == gcd(k, N)
           for N in range(1, 61) for k in range(1, N + 1))
print("faces = gcd(k, N) for every prism up to N = 60")

avg = {N: Fraction(sum(gcd(k, N) for k in range(1, N + 1)), N)
       for N in range(1, 1001)}
for N in sorted(avg, key=avg.get, reverse=True)[:3]:
    print(f"N = {N}: average {avg[N]} = {float(avg[N]):.4f}")

It prints

faces = gcd(k, N) for every prism up to N = 60
N = 840: average 195/14 = 13.9286
N = 720: average 63/5 = 12.6000
N = 900: average 182/15 = 12.1333