In a cube of side of length $9$ there are $1981$ points. Prove that there exist two of them situated at distance at most $1$ from each other.

Question

I guess this is a Pigeonhole Principle application. I tried dividing the cube in various ways, but got nowhere. Maybe there is another approach.

In a cube of side of length $9$ there are $1981$ points. Prove that there exist two of them situated at distance at most $1$ from each other.

Answer 1

If there would exist such a configuration with all distances $>1$ one could place 1981 balls of radius ${1\over2}$ in a cube $Q$ of side length 10 (move all faces of the given cube ${1\over2}$ outwards). But these balls have a total volume of $1037.24\ldots\ $.

In fact the number $1981$ can be improved to $1415$: If there are $N$ points with mutual distance $>1$ in the $9^3$-cube, then $N$ balls of radius ${1\over2}$ fit in the $10^3$-cube $Q$. These balls consume the fraction $$\delta={N\cdot{\pi\over6}\over 1000}$$ of ${\rm vol}(Q)$. By repeating this configuration periodically one obtains a sphere packing of space with this density; therefore by Hales' theorem one has $$\delta\leq{\pi\over 3\sqrt{2}}$$ or $N\leq1000\sqrt{2}\doteq1414.2$. This implies that for $N\geq1415$ such a configuration is impossible.

Answer 2

Assume $n$ points in the cube are each at distance at least $1$ from the others. Then the balls of radius $\frac12$ centered at these points are disjoint. Their total volume is $n$ times the volume $\frac43\pi\left(\frac12\right)^3=\frac16\pi$ of a ball of radius $\frac12$. On the other hand every point in one of these balls is at distance at most $\frac12$ from the cube of side $9$, in particular all the balls are included in a cube of side $10$. Hence $\frac16\pi n\leqslant 10^3$, that is, $n\leqslant1909$.