Can You Corral Your Hamster?

The Riddler for August 21, 2020. The Express asks whether a noisy signal count could have come from two independent sources, and the Classic optimises the shape of a hamster pen built from weighted posts and a fixed length of fabric.

Riddler Express

An astrophysics lab records signals in many equal intervals: zero signals in $45\%$ of intervals, one signal in $38\%$, and two signals in the remaining $17\%$. Your adviser suggests the pattern comes from two independent sources, each emitting a signal in any interval with some fixed probability. Could the data have come from two such sources?

The Riddler, FiveThirtyEight, August 21, 2020(original post)

Solution

Let the two sources fire independently with probabilities $p$ and $q$. Two signals means both fired, so $pq = 0.17$. Zero signals means neither fired, so $(1-p)(1-q) = 0.45$. Expanding the second equation, $1 - p - q + pq = 0.45$, and substituting $pq = 0.17$ gives $p + q = 0.72$. (The one-signal probability $p(1-q)+(1-p)q = (p+q)-2pq = 0.72 - 0.34 = 0.38$ is then automatic, so it carries no new information.)

So $p$ and $q$ are two numbers with sum $0.72$ and product $0.17$, hence the roots of $$x^2 - 0.72\,x + 0.17 = 0.$$ Its discriminant is $0.72^2 - 4(0.17) = 0.5184 - 0.68 = -0.1616 < 0$, so there are no real roots. No pair of probabilities $p, q \in [0,1]$ reproduces the data:

The computation

Encode the constraints directly: search the unit square for a pair $(p, q)$ with $pq = 0.17$ and $(1-p)(1-q) = 0.45$, and report the discriminant of the implied quadratic.

import numpy as np
A, B, C = 0.45, 0.38, 0.17          # P(0), P(1), P(2)
# p,q have sum s and product C with s from the zero-signal equation:
# (1-p)(1-q)=A  ->  1 - s + C = A  ->  s = 1 + C - A
s = 1 + C - A                        # = 0.72
disc = s*s - 4*C                     # discriminant of x^2 - s x + C
print(round(s, 4), round(disc, 4))   # 0.72 -0.1616  (negative)

# brute-force confirmation: no (p,q) on a fine grid meets both equations
grid = np.linspace(0, 1, 2001)
ok = [(p, q) for p in grid for q in grid
      if abs(p*q - C) < 1e-3 and abs((1-p)*(1-q) - A) < 1e-3]
print(len(ok))                       # 0

The discriminant is negative and the grid search finds no admissible pair, so the data cannot come from two independent sources.

Riddler Classic

You build a pen for your hamster by wrapping a fabric sheet around vertical posts. The sheet is $1$ metre long (so the perimeter is at most $1$ metre) and weighs $1$ kilogram; each post weighs $k$ kilograms. The combined weight of posts and fabric used cannot exceed $1$ kilogram. Using $n$ posts makes a regular $n$-gon of perimeter $1 - nk$. What is the greatest value of $k$ for which four posts enclose more area than three?

The Riddler, FiveThirtyEight, August 21, 2020(original post)

Solution

For a fixed perimeter the regular $n$-gon maximises area, so $n$ posts give a regular $n$-gon of perimeter $1 - nk$. Three posts ($3k$ in weight) leave $1 - 3k$ of fabric for an equilateral triangle of area $$A_3 = \frac{\sqrt3}{36}\,(1 - 3k)^2 ,$$ and four posts leave $1 - 4k$ for a square of area $$A_4 = \frac{1}{16}\,(1 - 4k)^2 .$$ Four posts beat three exactly while $A_4 > A_3$. The areas are equal when $$\frac{(1-4k)^2}{16} = \frac{\sqrt3\,(1-3k)^2}{36} \quad\Longleftrightarrow\quad \frac{1-4k}{4} = \frac{3^{1/4}}{6}\,(1-3k),$$ taking positive square roots (both pens have positive side length for small $k$). Solving the linear equation, $$1 - 4k = \tfrac{2}{3}\,3^{1/4}(1 - 3k) \;\Longrightarrow\; k = \frac{3 - 2\cdot 3^{1/4}}{12 - 6\cdot 3^{1/4}} .$$ Numerically this is $$\boxed{k = \dfrac{3 - 2\cdot 3^{1/4}}{12 - 6\cdot 3^{1/4}} \approx 0.08964 .}$$ Below this value the square wins; above it the triangle does (the heavier four-post frame eats too much of the budget).

The computation

Encode the two areas as functions of $k$ and solve $A_3 = A_4$ symbolically, then confirm the crossover by scanning $k$.

import sympy as sp
k = sp.symbols('k', positive=True)
A3 = sp.sqrt(3) * (1 - 3*k)**2 / 36
A4 = (1 - 4*k)**2 / 16
roots = [r for r in sp.solve(A3 - A4, k) if 0 < r < sp.Rational(1, 4)]
kc = roots[0]
print(sp.nsimplify(kc), float(kc))          # closed form, 0.0896422...

# scan: four posts win below kc, three posts win above it
f = sp.lambdify(k, A4 - A3)
for kk in [0.08, 0.0896, 0.092]:
    print(kk, 'four better' if f(kk) > 0 else 'three better')

The solver returns $k = (3 - 2\cdot 3^{1/4})/(12 - 6\cdot 3^{1/4}) \approx 0.08964$, and the scan confirms four posts win just below it and lose just above it.