Can You Join The World’s Biggest Zoom Call?

Riddler Express

Nine locations form a three-by-three grid. A special mask sounds whenever you are within some fixed (but unknown) distance of a Korok Seed. Each of the eight outer points is within range of a seed, but the centre point is not. What is the minimum possible number of Korok Seeds?

The Riddler, FiveThirtyEight, May 29, 2020(original post)

Solution

The detection distance is unknown, so a seed can sit anywhere, arbitrarily far from the grid; all that matters is which of the nine points fall inside a disk of that radius around each seed.

One seed cannot do it. If a single seed at point $P$ put all eight outer points in range while leaving the centre $M$ out, then $P$ would be closer to all eight outer points than to $M$. But the outer points come in opposite pairs through $M$: the left and right midpoints, say. If $P$ is nearer the right one than $M$, it lies on the right half-plane and so is nearer $M$ than the left one. No point can be closer to both members of an opposite pair than to their midpoint, so one seed is impossible.

Two seeds suffice. Place them far away in opposite directions, one off the top-right, one off the bottom-left. With a detection radius large enough, each seed’s disk sweeps in the four outer points nearest it while the centre, sitting between the two disks, falls in neither. So the minimum is $$\boxed{2}.$$

The computation

Encode the grid (centre at the origin, outer points at $(\pm1,0),(0,\pm1),(\pm1,\pm1)$). First show no single point can be closer to all eight outer points than to the centre. Then exhibit two seeds and a radius covering the eight outer points but not the centre.

import numpy as np
M = np.zeros(2)
outer = np.array([[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1.]])
P = np.random.default_rng(0).uniform(-6, 6, (3_000_000, 2))
dM = np.linalg.norm(P - M, axis=1)
closer_all = np.all([np.linalg.norm(P - L, axis=1) < dM for L in outer], axis=0)
print("points beating the centre on all 8 outer:", closer_all.sum())   # 0

ang = np.radians(30)              # off the 45-deg axes so every leaf projects nonzero
u = np.array([np.cos(ang), np.sin(ang)]); s1, s2 = 1000 * u, -1000 * u
def d(p, s): return np.linalg.norm(p - s)
r = max(min(d(L, s1), d(L, s2)) for L in outer)        # radius to catch every leaf
print("every leaf within r, centre farther than r?", r < min(d(M, s1), d(M, s2)))  # True

Riddler Classic

Everyone in the U.S. (about $330$ million people) joins one Zoom call between 8 and 9 a.m. Each person picks two independent uniform random times in that hour, joins at the earlier and leaves at the later. What is the probability that at least one attendee is on the call with everyone else (their interval overlaps every other interval)? Extra credit: that at least two are?

The Riddler, FiveThirtyEight, May 29, 2020(original post)

Solution

Start with two attendees. Four independent times are drawn; label them $A<B<C<D$ in order. Each attendee owns two of these four times (their join and leave), and the $\binom42 = 6$ ways to deal the four times split evenly. The two people fail to overlap only when one owns $\{A,B\}$ and the other $\{C,D\}$, that is in $2$ of the $6$ cases. So they overlap with probability $4/6 = \tfrac23$, and with two people one overlapping the other means both do.

The striking fact is that this $\tfrac23$ does not change as the crowd grows. Whether there are three attendees or $330$ million, the probability that at least one person overlaps everyone is $$\boxed{\tfrac23},$$ a result that follows from a swapping argument on the ordered join/leave times (it appears in a $1990$ paper on the problem). For the extra credit, the probability that at least two attendees each overlap everyone settles (for three or more people) at $$\boxed{\tfrac25}.$$ With exactly two people the two counts coincide at $\tfrac23$, since if one is universal so is the other; the $\tfrac25$ is the large-group value.

The computation

Encode the actual experiment: draw each person’s two times, form intervals, and count how many attendees overlap all others. Averaging over many trials gives $\tfrac23$ and $\tfrac25$, independent of the crowd size.

import numpy as np
def zoom(n, trials, seed=1):
    rng = np.random.default_rng(seed)
    one = two = 0
    for _ in range(trials):
        u = np.sort(rng.random((n, 2)), axis=1)
        a, b = u[:, 0], u[:, 1]
        universal = np.sum([(a <= b[i]).all() and (b >= a[i]).all() for i in range(n)])
        one += universal >= 1; two += universal >= 2
    return round(float(one) / trials, 3), round(float(two) / trials, 3)
for n in (3, 8, 50):
    print(n, zoom(n, 20000))         # ~ (0.667, 0.400)

The frequencies sit at about $0.667$ and $0.400$ for every crowd size, matching $\tfrac23$ and $\tfrac25$.