Chapter 60

Can You Climb Your Way To Victory?

Riddler Express

The sequence $1, 4, 4, 0, 4, 8, 0, 0, 4, 4, 8, \dots$ counts, for each $n = 0, 1, 2, \dots$ , the number of ways to write $n$ as an ordered sum of two squares of integers (signs allowed). What is the average value of the whole sequence?

Solution

Write $s(n)$ for the term: the number of integer solutions $(x, y)$ of $x^2 + y^2 = n$ . For instance $s(5) = 8$ , from $(\pm1, \pm2)$ and $(\pm2, \pm1)$ . The sequence is wildly irregular ( $s(n) = 0$ whenever $n \equiv 3 \pmod 4$ ), so a running average is the right thing to ask for. Summing the first $n+1$ terms counts all integer points with $x^2 + y^2 \le n$ , call it $t(n)$ , so the average of $s(0), \dots, s(n)$ is $\tfrac{t(n)}{n+1}$ . As $n$ grows this tends to a single clean value: $\lim_{n \to \infty} \frac{s(0) + \cdots + s(n)}{n+1} = \lim_{n \to \infty}\frac{t(n)}{n+1} = \boxed{\pi}.$

$\displaystyle\lim_{n \to \infty} \frac{t(n)}{n+1} = \pi$ , where $t(n) = \#\{(x,y) \in \mathbb{Z}^2 : x^2 + y^2 \le n\}$ .

Proof. This is Gauss’s circle argument. Place a unit square centred on each lattice point inside the disk of radius $\sqrt n$ ; the squares have total area $t(n)$ and roughly tile the disk. Every such square lies within distance $\tfrac{\sqrt2}{2}$ (half a diagonal) of its centre, so all the squares fit inside the disk of radius $\sqrt n + \tfrac{\sqrt2}{2}$ , and they cover the disk of radius $\sqrt n - \tfrac{\sqrt2}{2}$ . Comparing areas, $\pi\Big(\sqrt n - \tfrac{\sqrt2}{2}\Big)^2 \le t(n) \le \pi\Big(\sqrt n + \tfrac{\sqrt2}{2}\Big)^2.$ Dividing by $n+1$ and letting $n \to \infty$ , both bounds tend to $\pi$ , and the squeeze theorem finishes it. ■

The computation

Count lattice points inside the disk of radius $\sqrt n$ directly and watch $t(n)/(n+1)$ settle towards $\pi$ .

from math import isqrt, pi
def t(n):
    r = isqrt(n)
    return sum(1 for x in range(-r, r + 1) for y in range(-r, r + 1)
               if x*x + y*y <= n)
for n in (10, 100, 10_000, 1_000_000):
    print(n, t(n) / (n + 1))                   # -> 3.14159..., approaching pi
print(pi)

Riddler Classic

Eight climbers each get a rank $1$ through $8$ (no ties) in each of three events; a climber’s final score is the product of their three ranks, and lowest score wins. What is the highest score a climber could post and still be able to win or tie for first?

Solution

A climber can win with score $p$ only if every rival also scores at least $p$ , so the question is: how large can the smallest of the eight final scores be made? We want to assign the three rank-permutations to maximise the minimum product.

There is a ceiling. The eight final scores multiply to $(8!)^3$ , since each event contributes $8!$ , so their geometric mean is $(8!)^{3/8} \approx 53.4$ . The smallest score cannot exceed the geometric mean, so the best possible minimum is at most $53$ . A direct search over assignments shows the true ceiling is a little lower, and it is attainable: $\boxed{48}.$ So a climber scoring $48$ can still tie for gold, but $49$ or more cannot, because no arrangement of ranks keeps all eight products that high.

The computation

Fix the first event’s ranks as the identity (relabelling climbers). For each permutation of the second event, find the third-event permutation that maximises the minimum product, via a bottleneck assignment (keep only edges with product $\ge T$ and test for a perfect matching, raising $T$ as far as it will go).

from itertools import permutations
n, vals = 8, list(range(1, 9))
def perfect(adj):                       # Kuhn's matching, all rows matched?
    matchR = [-1]*n
    def aug(u, seen):
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                if matchR[v] == -1 or aug(matchR[v], seen):
                    matchR[v] = u; return True
        return False
    return all(aug(u, [False]*n) for u in range(n))
best = 0
for s2 in permutations(vals):
    W = [[(i + 1) * s2[i] * v for v in vals] for i in range(n)]
    cand = sorted({w for row in W for w in row})
    lo, hi, feas = 0, len(cand) - 1, 0
    while lo <= hi:                      # binary search the bottleneck
        mid = (lo + hi) // 2; T = cand[mid]
        if perfect([[c for c in range(n) if W[i][c] >= T] for i in range(n)]):
            feas = T; lo = mid + 1
        else:
            hi = mid - 1
    best = max(best, feas)
print(best)                             # 48