Who Will Win the Space Race?

The Riddler for March 10, 2017, both halves by Alex Bellos. The Express is the classic “a rope around the Earth, lengthened by 1 metre” geometry trick; the Classic is a symmetry-strategy coin game on a square table.

Riddler Express

A rope lies tightly around the Earth at the equator. The rope is then lengthened by exactly $1$ metre and raised uniformly so that it again forms a taut circle with the same centre. How high is the rope off the ground?

The Riddler, FiveThirtyEight, March 10, 2017(original post)

Solution

Let $R$ be the Earth’s radius and $r$ the small height we want. The old rope has length $2\pi R$ and the new rope has length $2\pi(R + r)$. The new rope is $1$ metre longer, so $$2\pi(R + r) = 2\pi R + 1.$$ Subtracting $2\pi R$ from both sides eliminates $R$ entirely: $$2\pi r = 1, \qquad r = \frac{1}{2\pi} \approx 0.1592 \text{ m}.$$ The Earth’s radius drops out because the linearity of circumference in radius means that the extra metre is distributed evenly over a circle whose “length” factor is $2\pi$. The answer is $$\boxed{\dfrac{1}{2\pi} \text{ m} \approx 15.92 \text{ cm}}.$$

The computation

Encode the problem itself: pick any plausible Earth radius and compute the radius of a concentric circle whose circumference is exactly $1$ metre longer. The new radius minus the old should be $1/(2\pi)$ for every choice of $R$.

import math
for R in [6_371_000, 1, 1e9, 7.13e6]:                # any positive radius
    new_R = (2 * math.pi * R + 1) / (2 * math.pi)
    print(f"R = {R:>12}, height = {new_R - R:.10f} m")
print(f"1 / (2 pi) = {1 / (2 * math.pi):.10f} m")
# every height is 0.1591549431 m, independent of R

Riddler Classic

Two players take turns placing identical, non-overlapping coins on a square table (each coin must lie entirely on the table, coins are not allowed to touch). The player who places the last coin wins. The table is larger than a single coin. Which player has a winning strategy, and what is it?

The Riddler, FiveThirtyEight, March 10, 2017(original post)

Solution

The first player wins, and the strategy uses a single symmetry. Place the first coin so that its centre coincides with the centre of the table. Thereafter, whenever the opponent puts down a coin at some position $P$ on the table, place the next coin at the point $P'$ obtained by rotating $P$ by $180^{\circ}$ about the centre of the table (equivalently, reflecting $P$ through the table’s centre). Call this the mirror move.

Why it works. After the first move, the set of coins on the table is symmetric under the central reflection $P \mapsto P'$ (one coin sits at the centre, which is its own reflection). Suppose, inductively, that this symmetry holds whenever it is the opponent’s turn. The opponent’s move puts a coin at some $P$. The mirror move puts a coin at $P'$. Both moves preserve the symmetry, so the inductive hypothesis holds again when it is the opponent’s next turn.

For the opponent’s move to be legal, $P$ must lie inside the table and the new coin must not touch any existing coin. By symmetry, $P'$ also lies inside the table, the central reflection takes the coin at $P$ to one at $P'$, and the coins it would have touched (those at positions $Q$) become coins at $Q'$. So the mirror move is legal whenever the opponent’s was, with one exception: if $P' = P$ (the opponent placed exactly at the centre), the mirror would land on the same spot. But the centre is occupied by the first coin, so the opponent cannot place there. So the mirror move is always legal whenever the opponent’s was.

The first player therefore always has a reply. The game must terminate (a finite number of coins fit on a bounded table), so the opponent runs out of legal moves first, and the first player places the last coin. The answer is

The computation

The strategy proof is essentially complete on the page, so the computation is a sanity check: simulate the game on a small table with random opponent play and confirm the first player wins every time when she follows the mirror rule.

1. Treat the table as a $[-1, 1] \times [-1, 1]$ square; coins are unit-radius scaled to a small $r$.

2. Maintain the list of placed coin centres.

3. Player 1 always opens at $(0, 0)$.

4. Player 2 picks a random legal position on a fine grid.

5. Player 1 plays the central reflection of the latest move.

6. Whoever cannot legally move loses.

import random
def legal(p, placed, r):
    x, y = p
    if abs(x) + r > 1 or abs(y) + r > 1: return False
    return all((x - a)**2 + (y - b)**2 > (2 * r)**2 for a, b in placed)

def play(r, seed):
    rng = random.Random(seed)
    placed = [(0.0, 0.0)]                            # P1's opening move
    grid = [(-1 + 2 * i / 40, -1 + 2 * j / 40) for i in range(41) for j in range(41)]
    turn = 2
    while True:
        if turn == 2:
            opts = [p for p in grid if legal(p, placed, r)]
            if not opts: return 1                    # P1 wins (P2 has no move)
            opp = rng.choice(opts); placed.append(opp); turn = 1
        else:
            mirror = (-opp[0], -opp[1])
            if not legal(mirror, placed, r): return 2
            placed.append(mirror); turn = 2

wins = sum(play(0.15, s) == 1 for s in range(200))
print(f"P1 wins {wins}/200 random P2 plays")
# P1 wins 200/200