= Solution
For five points, partition the <unit square> into four <squares> of side $1/2$. Assign boundary points to just one neighbouring piece. By the <pigeonhole principle>, two of the points lie in one piece, whose <diameter> is its diagonal, $\sqrt{(1/2)^2+(1/2)^2}=\sqrt2/2$.
For eight points, use seven smaller-<diameter> pieces rather than eight <rectangles>. Start with the convex <pentagon>
$$
P=\operatorname{conv}\{(0,0),(1/2,0),(1/2,1/4),(1/4,1/2),(0,1/4)\}.
$$
Take its four reflected copies at the corners of the <square>. The remaining pieces are the left <triangle> with vertices $(0,1/4),(1/4,1/2),(0,3/4)$, its right-hand <reflection>, and the central diamond with vertices $(1/4,1/2),(1/2,1/4),(3/4,1/2),(1/2,3/4)$. These seven <polygons> cover the <square> with disjoint interiors. To verify coverage directly, for $0\leq y\leq1/4$ the two bottom pentagons split the horizontal section at $x=1/2$. For $1/4\leq y\leq1/2$, the five successive sections have endpoints $0,y-1/4,3/4-y,y+1/4,5/4-y,1$ and belong respectively to the left triangle, bottom-left pentagon, diamond, bottom-right pentagon and right triangle. Reflection gives the top half.
The <diameter of a finite convex hull> is the greatest <distance> between its vertices: if two points are <convex combinations> of vertices, their difference is a <convex combination> of <vertex> differences, and the <triangle inequality> bounds its <norm> by the largest such <distance>. Checking the five vertices of $P$ gives <diameter> $\sqrt{(1/2)^2+(1/4)^2}=\sqrt5/4$; <reflections> preserve that value. Each remaining <triangle> and the diamond has <diameter> $1/2$, which is smaller. After assigning shared boundaries to one piece, eight points in these seven pieces force a pair in a common piece. Hence \b[some pair is at <distance> at most $\sqrt5/4$].
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/discrete-mathematics-continuous-mathematics-and-probability-resit-square-partitions.png]
{title=Four and seven regions give the two distance bounds by the pigeonhole principle}
Both arguments are instances of a <pigeonhole distance bound from a partition>.
Back to article page
