Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/discrete-mathematics-continuous-mathematics-and-probability-resit/3/d/solution

For five points, partition the unit square into four squares of side . 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, .
For eight points, use seven smaller-diameter pieces rather than eight rectangles. Start with the convex pentagon
Take its four reflected copies at the corners of the square. The remaining pieces are the left triangle with vertices , its right-hand reflection, and the central diamond with vertices . These seven polygons cover the square with disjoint interiors. To verify coverage directly, for the two bottom pentagons split the horizontal section at . For , the five successive sections have endpoints 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 gives diameter ; reflections preserve that value. Each remaining triangle and the diamond has diameter , which is smaller. After assigning shared boundaries to one piece, eight points in these seven pieces force a pair in a common piece. Hence some pair is at distance at most .
Figure 1.
Four and seven regions give the two distance bounds by the pigeonhole principle
. Details.
Both arguments are instances of a pigeonhole distance bound from a partition.

New to topics? Read the docs here!