Are You A Pinball Wizard?

The Riddler for July 24, 2020. The Express is an electoral-college puzzle: how few popular votes can still win Riddler Township’s election? The Classic is a geometric pinball game between a wall and a circle, asking for the most bounces possible.

Riddler Express

Riddler Township’s ten shires have populations $11, 21, 31, \ldots, 101$ and electoral votes $3, 4, 5, \ldots, 12$ respectively (two votes plus one per ten citizens). With two candidates and every citizen voting, what is the lowest percentage of the popular vote with which a candidate can still win the election?

The Riddler, FiveThirtyEight, July 24, 2020(original post)

Solution

There are $3 + 4 + \cdots + 12 = 75$ electoral votes, so winning needs a majority of $38$. To spend the fewest popular votes, a candidate wins a chosen set of shires by the barest majority and loses the rest with zero votes. Shire of population $p$ (all odd here) takes $\tfrac{p+1}{2}$ votes to carry, while delivering its fixed electoral votes, so the goal is to reach $38$ electoral votes for the least total $\tfrac{p+1}{2}$, a small knapsack.

The least-populous shires are the most efficient: Oneshire trades $6$ votes for $3$ electors ($0.5$ per vote), whereas Tenshire trades $51$ votes for $12$ ($0.24$ per vote). Carrying Oneshire, Threeshire, Fourshire, Fiveshire, Sixshire and Sevenshire gives exactly $3+5+6+7+8+9 = 38$ electoral votes for $6+16+21+26+31+36 = 136$ popular votes, and no cheaper combination reaches $38$. Against the township’s $11 + 21 + \cdots + 101 = 560$ citizens, that is $$\frac{136}{560} \approx \boxed{24.3\%}.$$

The computation

Encode the knapsack: over every subset of shires whose electoral votes reach $38$, minimise the bare-majority popular votes.

pops = [11, 21, 31, 41, 51, 61, 71, 81, 91, 101]
ev = [2 + round(p/10) for p in pops]
best = min(sum((pops[i] + 1)//2 for i in range(10) if m >> i & 1)
           for m in range(1 << 10)
           if sum(ev[i] for i in range(10) if m >> i & 1) >= 38)
print(best, f"{100*best/sum(pops):.1f}%")     # 136  24.3%

The minimum is $136$ popular votes out of $560$, about $24.3\%$, as boxed.

Riddler Classic

Riddler Pinball has an infinite straight wall and a fixed circle of radius $1$ whose centre is $2$ inches from the wall. A ball starts $2$ inches from the wall and $2$ inches from the circle’s centre, and you flick it toward a point on the wall a distance $x$ from the wall’s closest point to the circle. Collisions are perfectly elastic. What is the greatest number of bounces you can achieve, and at what $x$?

The Riddler, FiveThirtyEight, July 24, 2020(original post)

Solution

Place the wall on the line $y = 0$ and the circle’s centre at $(0,2)$, so its lowest point is $(0,1)$, one inch above the wall. The ball starts at $(2,2)$.

The key object is a hidden periodic orbit: a ball bouncing straight up and down forever in the one-inch gap between the circle’s bottom point $(0,1)$ and the wall point $(0,0)$. This orbit is unstable, because the circle is curved: the tiniest sideways lean grows at every bounce off the circle, so a ball started almost vertically drifts a little further each bounce until it finally leaks out of the gap and escapes. Now run that leak backwards. Reversing such an escaping trajectory gives a ball that comes in from outside, bounces its way toward the vertical orbit, lingers for many bounces, and then comes back out. The closer the aim is to the one critical value that would feed the ball exactly onto the vertical orbit, the longer it lingers, and the lingering can be made as long as we like. So the number of bounces has no maximum: $$\boxed{\text{infinitely many (unbounded)}},$$ approached as $x \to x^* \approx 0.82248632494339\ldots$, an irrational value with no finite decimal. Aim a hair off and the ball leaks out after finitely many bounces; aim closer and you gain more, without limit.

The computation

Encode the billiard directly: reflect off the wall (flip the vertical velocity) and off the circle (reflect across the radius), and count bounces until the ball escapes. Aiming at the published approximation of $x^*$ already yields $43$ bounces, and adding digits pushes the count higher without bound.

import math
C, R = (0.0, 2.0), 1.0
def step(p, v):
    tw = -p[1]/v[1] if v[1] < 0 else math.inf            # time to wall y=0
    dx, dy = p[0]-C[0], p[1]-C[1]
    bb = 2*(dx*v[0] + dy*v[1]); cc = dx*dx + dy*dy - R*R
    tc, disc = math.inf, (2*(dx*v[0]+dy*v[1]))**2 - 4*(v[0]**2+v[1]**2)*cc
    if disc >= 0:
        sq = math.sqrt(disc)
        for t in ((-bb-sq)/2/(v[0]**2+v[1]**2), (-bb+sq)/2/(v[0]**2+v[1]**2)):
            if 1e-9 < t < tc: tc = t
    if 1e-9 < tw < tc:                                    # bounce off wall
        return (p[0]+tw*v[0], 0.0), (v[0], -v[1])
    if tc < math.inf:                                    # bounce off circle
        q = (p[0]+tc*v[0], p[1]+tc*v[1])
        nx, ny = (q[0]-C[0])/R, (q[1]-C[1])/R
        d = v[0]*nx + v[1]*ny
        return q, (v[0]-2*d*nx, v[1]-2*d*ny)
    return None, None                                    # escape
def bounces(x, maxb=200):
    p = (2.0, 2.0); v = (x-2.0, -2.0); n = math.hypot(*v); v = (v[0]/n, v[1]/n)
    c = 0
    for _ in range(maxb):
        p, v = step(p, v)
        if p is None: break
        c += 1
    return c
print(bounces(0.75), bounces(0.9), bounces(0.82248632494339))   # 4 4 43

The two off-target aims give $4$ bounces each, while $x \approx 0.82248632494339$ gives $43$; refining $x$ toward $x^*$ raises the count without limit, so the greatest number of bounces is unbounded.