Can You Connect The Dots?

Riddler Express

Driving north on a grid, at each intersection you turn left or right, each with probability $\tfrac12$. After $10$ intersections, what is the probability you are again driving north? Extra credit: if at each intersection you instead go left, right, or straight, each with probability $\tfrac13$, what is the probability after $10$ intersections?

The Riddler, FiveThirtyEight, June 26, 2020(original post)

Solution

Track the heading as a number $\bmod 4$ (north $=0$, east $=1$, south $=2$, west $=3$). A left turn adds $3$, a right turn adds $1$; you face north again when the turns sum to a multiple of $4$.

With only left and right turns, every turn is $\pm 1$, so after $10$ turns the heading is $\sum \pm 1 \bmod 4$, which is even, hence north or south, never east or west. The sum is a multiple of $4$ exactly when the number of right turns is odd, and among $10$ fair turns that happens half the time: $$\boxed{\tfrac12}.$$ The extra credit adds a “straight” move ($+0$). Using the roots-of-unity filter, the probability of returning to north after $10$ steps is $\tfrac14\sum_{j=0}^{3}\bigl(\tfrac{\omega^j + \omega^{-j} + 1}{3}\bigr)^{10}$ with $\omega = i$, in which the $j=0$ term gives $1$ and the others contribute $3^{-9}$: $$\frac14\Bigl(1 + 3\cdot 3^{-10}\Bigr) = \frac{4921}{19683} \approx \boxed{0.2500}.$$ The straight option pulls the answer almost exactly to $\tfrac14$: with three turn choices the four headings are nearly equally likely after ten steps.

The computation

Encode the heading as a state $\bmod 4$ and propagate the exact probability distribution over $10$ turns, for both turn rules.

from fractions import Fraction as F
from collections import defaultdict
def north_after(moves, steps=10):
    dist = defaultdict(lambda: F(0)); dist[0] = F(1)
    for _ in range(steps):
        nd = defaultdict(lambda: F(0))
        for h, pr in dist.items():
            for mv in moves: nd[(h + mv) % 4] += pr * F(1, len(moves))
        dist = nd
    return dist[0]
print(north_after([1, 3]))          # 1/2   (left/right only)
print(north_after([1, 3, 0]))       # 4921/19683 ~ 0.2500  (with straight)

Riddler Classic

Polly connects six unlabelled dots into a hexagon, and finds many different (non-self-intersecting) hexagons on the same six points. What is the greatest possible number of unique hexagons on six points? (Hint: with four points, the answer is three.) Extra credit: the greatest number of heptagons on seven points?

The Riddler, FiveThirtyEight, June 26, 2020(original post)

Solution

A hexagon on six fixed points is a cyclic ordering of them, and there are $5!/2 = 60$ such orderings (a cycle read in either direction is the same hexagon). Most of these self-intersect; Polly wants the simple ones, whose edges do not cross. The count depends on where the points lie, and it is largest not when the points are spread out but when they are nested: the record is set by putting three points inside the triangle formed by the other three.

For that arrangement the number of simple hexagons is $$\boxed{29},$$ and for seven points (where there are $6!/2 = 360$ orderings) the maximum is $$\boxed{92}.$$ These are the first entries of OEIS sequence A063546, the largest number of crossing-free Hamiltonian cycles on $n$ points (Aichholzer’s enumerations): $1, 3, 8, 29, 92, 339, \ldots$ for $n = 3, 4, 5, 6, 7, 8, \ldots$

The computation

Encode a hexagon as a cyclic order, and call it simple when no two non-adjacent edges cross (a standard segment-intersection test). Count the simple orderings for an optimal nested configuration of six points, and of seven points.

from itertools import permutations, combinations
def crosses(a, b, c, d):
    def turn(p, q, r): return (q[0]-p[0])*(r[1]-p[1]) - (q[1]-p[1])*(r[0]-p[0])
    return (turn(c, d, a) > 0) != (turn(c, d, b) > 0) and \
           (turn(a, b, c) > 0) != (turn(a, b, d) > 0)
def simple_count(pts):
    n = len(pts); total = 0
    for perm in permutations(range(1, n)):
        o = (0,) + perm
        if o[1] > o[-1]: continue                       # one direction per cycle
        e = [(o[i], o[(i + 1) % n]) for i in range(n)]
        if all(not crosses(pts[a], pts[b], pts[c], pts[d])
               for (a, b), (c, d) in combinations(e, 2)
               if len({a, b, c, d}) == 4):
            total += 1
    return total
hex6 = [(0,0),(12,0),(6,11),(4,3),(8,2),(6,6)]           # 3 points inside a triangle
hep7 = [(0,0),(20,0),(10,19),(15,2),(17,2),(15,6),(12,3)]
print(simple_count(hex6))     # 29
print(simple_count(hep7))     # 92