Given any five points in the interior of a square side 1, show that two of the points are a distance apart less than k = 1/√2. Is this result true for a smaller k?
Let the square be ABCD and O its midpoint. Let the midpoints of AB, BC, CD, DA be P, Q, R, S respectively. Then ABCD is the union of the 4 smaller squares: APOS, BQOP, CROQ, DSOR, each with diameter k. At least one of the smaller squares must contain two points. So the two points are a distance apart ≤ k. However, they cannot be a distance k apart, because the only pairs of points in a square realizing the diameter distance are opposite corners and they are not in the interior of ABCD. Hence the two points are a distance < k.
Take one point at O and the others on the main diagonals a distance ε from the corners. Then shortest distance between two points is k - ε which can be made arbitarily close to k.
14th Putnam 1954
© John Scholes
26 Nov 1999