Ten Points, Disjoint Disks

Problem

Your adversary chooses 10 points on the plane, and your mission is to cover them with disjoint unit disks. If the points are close together, it’s easy: one disk will cover them all. If they’re far apart, you can cover each point with its own disk. Can you always do it?

Credit: Peter Winkler, Monthly Mindbenders, National Museum of Mathematics, April 2026. Devised by Naoki Inaba and sent by Iwasawa Hirokazu.

Where the difficulty is not

The answer is yes, always. Before the proof, the two easy cases in the statement deserve a moment, because they mark out the region where nothing interesting happens.

Ten points inside a disk of radius $1$ need exactly one disk. At the other extreme, ten points at mutual distances greater than $2$ can each be given a private disk: two unit disks are disjoint as soon as their centres are more than $2$ apart, so centring a disk on each point works. The awkward configurations are the middling ones, points sitting a little more than $2$ apart, where a disk placed to catch one point sits in the way of the disk you wanted for the next.

That is a warning about method rather than about geometry. Any procedure that handles the points one at a time, committing to a disk before looking at what remains, will meet a configuration that defeats it. So the argument below does not handle them one at a time. It fixes every disk in advance, before looking at the points at all.

The packing

Take the densest packing of unit disks in the plane: centres on a triangular lattice with nearest-neighbour spacing $2$, so neighbouring disks are tangent and no two overlap. Disjointness is built in, and it survives any rigid motion of the whole packing.

The fundamental cell of that lattice is a rhombus of area $2\sqrt{3}$ containing exactly one disk, of area $\pi$. So the packing covers a fraction $\frac{\pi}{2\sqrt{3}} = 0.9068996\ldots$ of the plane, and the part it misses, the curved triangular gaps where three tangent disks meet, has density $1 - \frac{\pi}{2\sqrt{3}} = 0.0931003\ldots$

One line of expectation

Now randomise, and mind the order of play. The adversary commits to the ten points $p_1, \dots, p_{10}$ first. Only then do you draw a vector $T$ uniformly at random from one fundamental cell and translate the entire packing by $T$.

Fix any one point $p_i$. Translating the packing by a uniform vector of the cell is the same as holding the packing still and putting $p_i$ at a uniformly random position within a cell, so $\Pr(p_i \text{ is uncovered}) = 1 - \frac{\pi}{2\sqrt{3}} = 0.0931003\ldots$ exactly, wherever $p_i$ happens to be. Let $N$ count the points left uncovered, $N = \sum_{i=1}^{10} \mathbf{1}\{p_i \text{ uncovered}\}.$ Linearity of expectation asks for no independence among those ten indicators, which is what makes the argument work against an adversary: the points may be arranged however you like, in clusters, on a lattice, or in the gaps of some packing the adversary has in mind, and they may have been chosen with full knowledge of the strategy. Either way, $\mathbb{E}[N] = 10\left(1 - \frac{\pi}{2\sqrt{3}}\right) = 0.93100\ldots < 1.$

$N$ is a non-negative integer. If $N \ge 1$ for every translation, then $\mathbb{E}[N] \ge 1$. Since the mean is strictly below $1$, some translation must give $N = 0$. That translation puts all ten points inside disks of a packing whose disks are pairwise disjoint. Discard the disks that contain no point, and what is left is a family of disjoint unit disks covering the ten points.

The quantifiers carry the weight. The adversary moves first, the expectation is then computed for that fixed configuration, and the bound $\mathbb{E}[N] < 1$ holds for every configuration whatsoever. Reverse the order, let the adversary see $T$ before placing the points, and it drops all ten into the gaps.

Why ten

The number ten did not enter the calculation until the last line. For $n$ points, $\mathbb{E}[N] = n\left(1 - \frac{\pi}{2\sqrt{3}}\right) = 0.0931003\,n,$ which stays below $1$ exactly while $n \le 10$, since $1/0.0931003\ldots = 10.741$. Either side of the threshold:

$n$	$\mathbb{E}[N]$	below $1$?
$10$	$0.9310$	yes
$11$	$1.0241$	no

So the puzzle is set at the last value where this argument works, which is presumably why it says ten and not nine or twelve.

It matters to say precisely what happens at eleven. The bound fails, and that is all. A mean of $1.0241$ is entirely compatible with $\Pr(N = 0)$ being large, since a random variable can have mean above $1$ and still be zero most of the time. The failure at $n = 11$ is a failure of this proof, not a proof of failure. It produces no eleven points that defeat you, and whether every set of $n$ points admits a cover by disjoint unit disks for $n \ge 11$ is a harder question that nothing here settles in either direction.

Pushing the positive result past ten would mean improving on a fixed lattice: allowing rotations as well as translations, using non-lattice packings, or bringing in the geometry of the particular configuration rather than the covering density alone. Settling it the other way would mean exhibiting a configuration and proving that no arrangement of disjoint unit disks covers it, something a density bound cannot do, since it says nothing about any particular set of points.

Computational verification

The proof asserts that a covering translation exists without showing one, so the honest check searches for it. The code below builds the packing from scratch (triangular lattice, spacing $2$, a point covered when it lies within distance $1$ of some centre) and tries random translations against three families of ten-point configurations: points scattered in a box of side $5$, points on a triangular lattice of spacing $2.1$ (mutual distances just above the awkward threshold), and points placed at the gap centres of the untranslated packing, where the distance to the nearest disk centre is as large as it can be.

The last line asks a separate question: how often does a single random translation work? The proof’s guarantee, via Markov’s inequality, is only $1 - \mathbb{E}[N] = 0.069$.

import numpy as np

A1, A2 = np.array([2.0, 0.0]), np.array([1.0, np.sqrt(3)])
IJ  = np.mgrid[-9:10, -9:10].reshape(2, -1).T.astype(float)
CEN = IJ @ np.vstack([A1, A2])            # triangular lattice, spacing 2
FRAC = np.pi / (2*np.sqrt(3))             # one disk per cell of area 2 sqrt 3
print(f"covered fraction pi/(2 sqrt 3) = {FRAC:.4f}")
for n in (10, 11):
    e = n*(1 - FRAC)
    print(f"  n={n}: E[N] = {e:.4f}  {'<' if e < 1 else '>='} 1")

def nunc(pts, t):                         # points outside every unit disk
    return int((np.linalg.norm(pts[:,None] - (CEN+t), axis=2).min(1) > 1).sum())

rng = np.random.default_rng(20260416)
H = np.vstack([CEN + [1, np.sqrt(3)/3], CEN + [1, -np.sqrt(3)/3]])
H = H[np.argsort((H**2).sum(1))][:10]     # ten gap centres of the packing

def config(kind):                         # ten adversary points
    if kind == "box":
        return rng.uniform(0, 5, (10, 2))
    base = 1.05*CEN[np.argsort((CEN**2).sum(1))][:10] if kind[0] == "s" else H
    a = rng.uniform(0, 2*np.pi)           # random rotation and offset
    R = np.array([[np.cos(a), -np.sin(a)], [np.sin(a), np.cos(a)]])
    return base @ R.T + rng.uniform(0, 2, 2)

for kind in ("box", "spacing 2.1", "gap sites"):
    tries, ok = [], 0
    for _ in range(400):
        P = config(kind)
        for k in range(1, 20001):         # draw translations until one covers
            if nunc(P, rng.random()*A1 + rng.random()*A2) == 0:
                tries.append(k); ok += 1; break
    print(f"{kind:>11}: covered {ok}/400 configs,"
          f" mean {np.mean(tries):.1f} translations")

P = config("gap sites")                   # hardest family, many translations
hits = sum(nunc(P, rng.random()*A1 + rng.random()*A2) == 0 for _ in range(20000))
print(f"P(one random translation works) = {hits/20000:.3f}"
      f"  vs bound 1-E[N] = {1 - 10*(1-FRAC):.3f}")
# covered fraction pi/(2 sqrt 3) = 0.9069
#   n=10: E[N] = 0.9310  < 1
#   n=11: E[N] = 1.0241  >= 1
#         box: covered 400/400 configs, mean 2.7 translations
# spacing 2.1: covered 400/400 configs, mean 2.5 translations
#   gap sites: covered 400/400 configs, mean 2.9 translations
# P(one random translation works) = 0.271  vs bound 1-E[N] = 0.069

Family	Covered	Mean translations tried
random in a box of side $5$	$400/400$	$2.7$
lattice, spacing $2.1$	$400/400$	$2.5$
gap centres of the packing	$400/400$	$2.9$

All $1200$ configurations were covered, and the average search took fewer than three draws. The distance between the measured $0.271$ and the guaranteed $0.069$ is the ordinary slack in a bound of this kind: Markov’s inequality knows only the mean of $N$ and has to assume the worst about the rest of the distribution, while the actual distribution of $N$ concentrates on $0$ and $1$. The proof asks for none of that slack. It asks only that the mean fall below one, which for ten points, and by a margin of $0.069$, it does.