Beware The Hot Pumpkin

The Riddler for October 30, 2020. The Express is a goat-grazing area problem dressed as an election-official’s string, and the Classic is a Josephus-style elimination game whose clues pin down a single counting number by the Chinese remainder theorem.

Riddler Express

A polling site is a square building, $100$ feet on each side. A string $100$ feet long is tied to a door at the middle of one side; you hold the free end. The string cannot pass through the building. What is the area of the region outside the building you can reach?

The Riddler, FiveThirtyEight, October 30, 2020(original post)

Solution

In front of the door’s wall the string sweeps freely: a semicircle of radius $100$, area $\tfrac12\pi(100)^2 = 5000\pi$. The door sits $50$ feet from each corner of that wall. To reach past a corner you lay $50$ feet of string along the wall, leaving $50$ feet to swing around the corner, a quarter-circle of radius $50$ on each adjacent side. The two quarter-circles together make a semicircle of radius $50$, area $\tfrac12\pi(50)^2 = 1250\pi$. (Fifty feet does not reach the far corners, so the string never wraps a second time.) The total is $$5000\pi + 1250\pi = 6250\pi \approx \boxed{19{,}635 \text{ square feet}}.$$ This is a “goat grazing” problem: the building’s corners snag the tether, replacing the would-be full circle ($10{,}000\pi$) with the smaller wrapped region.

The computation

Encode the three pieces (front semicircle plus two corner quarter-circles) and sum.

import math
front = 0.5 * math.pi * 100**2        # semicircle, radius 100
corners = 2 * 0.25 * math.pi * 50**2  # two quarter-circles, radius 50
total = front + corners
print(round(total / math.pi, 6), round(total))   # 6250.0 (=6250*pi)  19635

The reachable area is $6250\pi \approx 19{,}635$ square feet.

Riddler Classic

You and $60$ friends ($61$ players) sit in a circle and fix a positive integer $N$. Starting with you counting “1” and passing left, the player who says “$N$” is eliminated; the next player restarts the count at $1$, and so on until one remains. The first eliminated player is $18$ seats to your left; the second is $31$ seats to the left of the next starter; the third starter is eliminated immediately (counts up to $N$ landing back on himself). What is the smallest $N$ consistent with this?

The Riddler, FiveThirtyEight, October 30, 2020(original post)

Solution

Each round, the count wraps the circle some whole number of times and then stops on the eliminated player. Counting includes the starter, so reaching the player $k$ seats to the starter’s left means $k+1$ people have counted off (the starter plus $k$ others).

• Round 1, $61$ players, eliminated $18$ seats left: $N \equiv 18 + 1 = 19 \pmod{61}$.

• Round 2, $60$ players, eliminated $31$ seats left: $N \equiv 31 + 1 = 32 \pmod{60}$.

• Round 3, $59$ players, the starter eliminates himself: $N \equiv 1 \pmod{59}$.

The moduli $59, 60, 61$ are pairwise coprime, so the Chinese remainder theorem gives a unique $N$ modulo $59 \cdot 60 \cdot 61 = 215{,}940$. Solving the system $$N \equiv 19 \!\pmod{61},\; N \equiv 32 \!\pmod{60},\; N \equiv 1 \!\pmod{59}$$ yields $$\boxed{N = 136{,}232}.$$

The computation

Encode the three congruences and solve them by the Chinese remainder theorem.

from sympy.ntheory.modular import crt
moduli = [61, 60, 59]
residues = [19, 32, 1]
N, M = crt(moduli, residues)
print(int(N), int(M))                 # 136232  215940
# brute-force check
print(min(n for n in range(1, 215941)
          if n % 61 == 19 and n % 60 == 32 and n % 59 == 1))   # 136232

The smallest consistent count is $N = 136{,}232$.